この問題はダイナミックプログラミングを用いて解決した.従来のダイナミックプログラミングとは少し異なり,記録を行った.(n+1)*(m+1)のリストを作成し,nで巡回し,1行のリストを巡回する.巡る前にdp[0][s]を1に変換します.次に、繰り返して、ボリュームの可能な位置のすべての要素を1に更新し、dp[-1]リストを表示し、正解が1の最大インデックスを出力します.
点火式はdp[i-1][j]이 1일 때, dp[i][j+v[i-1]]=1, dp[i][j-v[i-j]]=1です.

n,s,mと入力します.

vリストを入力します.

dpを(n+1)*(m+1)リストとして宣言し、0に入力します.

dp[0][s]を1に更新します.(現在0の場合のボリュームはs)

1からnまで繰り返されるiに対してfor文を行う.
->m jのfor文を繰り返す.
-->dp[i-1][j]が0の場合、次の反復が行われる.
-->j+v[i-1]がm以下の場合は、dp[i]j+v[i-1]を1に更新します.
-->j-v[i-1]が0以上の場合は、dp[i]j-v[i-1]を1に更新します.

mから0までの繰返し減少のiに対してfor文を回す.
->dp[1][i]が1の場合、iを出力して重複文を終了します.

を除き、-1を出力します.

Code

n, s, m=map(int, input().split())
v=list(map(int, input().split()))
dp=[[0]*(m+1) for _ in range(n+1)]
dp[0][s]=1
for i in range(1, n+1):
    for j in range(m+1):
        if dp[i-1][j]==0:
            continue
        if j+v[i-1]<=m:
            dp[i][j+v[i-1]]=1
        if j-v[i-1]>=0:
            dp[i][j-v[i-1]]=1
for i in range(m, -1, -1):
    if dp[-1][i]==1:
        print(i)
        break
else:
    print(-1)