题解 | #点菜问题#

while True:
    try:
        m, n = map(int, input().split(" "))
        w = [0 for i in range(n)]  # 钱大小
        v = [0 for i in range(n)]  # 分数
        dp = [0 for i in range(m + 1)]
        for i in range(n):
            w[i], v[i] = map(int, input().split(" "))
        for i in range(n):
            for j in range(m, w[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - w[i]] + v[i])
        print(dp.pop())
    except:
        break