经典一维滚动数组 DP，关键在容量必须倒序遍历：

dp[j] 表示「容量为 j 时的最大总价值」

对每件物品：dp[j] = max(dp[j], dp[j-w] + c)，j 从 M 递减到 w

倒序保证每件物品只用一次（正序会变成完全背包，同一件能反复装）

状态转移含义：要么不装第 i 件（dp[j]），要么装（dp[j-w] + c，腾出 w 容量）。

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)
    M = int(next(it))   # 背包容量
    N = int(next(it))   # 物品数量

    # dp[j] = 容量为 j 时的最大总价值
    dp = [0] * (M + 1)

    for _ in range(N):
        w = int(next(it))
        c = int(next(it))
        # 0/1 背包：容量倒序遍历，保证每件物品只用一次
        for j in range(M, w - 1, -1):
            if dp[j - w] + c > dp[j]:
                dp[j] = dp[j - w] + c

    sys.stdout.write(str(dp[M]) + "\n")

if __name__ == "__main__":
    main()