题解 | #点菜问题#

def best(c, p, v, n):
    dp = [0]*(c+1)
    dp[0] = 0
    for i in range(0, n):
        for j in range(c, p[i]-1, -1):
            dp[j] = max(dp[j], dp[j-p[i]] + v[i])
    print(dp[c])

while True:
    try:
        price = []
        vi = []
        c, n = map(int, input().split())
        for i in range(n):
                p, v = map(int, input().split())
                price.append(p)
                vi.append(v)
        best(c, price, vi, n)
    except:
        break