[백준] 기타리스트.py

import sys
N, S, M = map(int, sys.stdin.readline().split())
V = list(map(int, sys.stdin.readline().split()))

# 모든 볼륨에 관해 연주 가능 여부를 계산하기.
result = [[0 for _ in range(M+1)] for _ in range(N+1)]
result[0][S] = 1

# 정확히 이렇게 풀어아먄 메모리 초과도, 시간 초과도 안 난다.
for i in range(1, N+1):
    for j in range(M+1):
        if result[i-1][j] == 0:
            continue
        if j + V[i-1] <= M:
            result[i][j+V[i-1]] = 1
        if j - V[i-1] >= 0:
            result[i][j-V[i-1]] = 1
            
idx = -1
for i in range(M, -1 , -1):
    if result[-1][i] == 1:
        idx = i
        break
print(idx)