문제
유니스트 컴퓨터공학과에 다니는 서윤이는 이번에 어떤 과목을 들을지 고민중이다. 학점을 잘 받을 수 있으면서도 중요한 과목을 듣고 싶은 서윤이는 모든 과목의 중요도와, 일정 이상의 학점을 받기 위해 필요한 공부시간을 다 적었다.
처음에는 모든 과목을 들으려고 했던 서윤이는 자신의 공부 시간에 한계가 있다는 것을 깨달았다. 그래서, 공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.
중요도가 최대가 되도록 과목을 선택했을 때, 최대가 되는 중요도를 출력하는 프로그램을 작성하시오.
# 17845
import sys
input = lambda: sys.stdin.readline().strip()
n, k = map(int, input().split())
sub = [list(map(int, input().split())) for _ in range(k)]
sub.sort(key = lambda x:x[0], reverse = True)
sub.sort(key = lambda x:x[1])
knapsack = [[0] * (n+1) for _ in range(k+1)]
for i in range(1, k+1):
imp, time = sub[i-1][0], sub[i-1][1]
if time > n:
break
knapsack[i][time] = max(knapsack[i-1][time], imp)
for j in range(n+1):
if time > j:
knapsack[i][j] = knapsack[i-1][j]
else:
knapsack[i][j] = max(knapsack[i-1][j-time] + imp, knapsack[i-1][j])
max_imp = 0
for i in range(1, k+1):
max_imp = max(max_imp, knapsack[i][n])
print(max_imp)