题解 | #采药#

def best(sum, time, value, n):
    dp = [0]*(sum+1)
    dp[0]=0
    for i in range(0, n):
        for j in range(sum, time[i]-1, -1):
            dp[j] = max(dp[j], dp[j-time[i]] + value[i])
    return dp[sum]
while True:
    try:
        t1 = []
        v = []
        t, m = map(int, input().split())
        for i in range(m):
            time, value = map(int, input().split())
            t1.append(time)
            v.append(value)

        res = best(t, t1, v, m)
        print(res)
    except:
        break