该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】在0/1背包问题中，需对容量C的背包进行装载，从N个物品中选取装入背包的物品，每件物品i(1<=i<=n)的重量为WI，价值为PI，你的任务是，编写程序计算：在满足背包中所有物品的总重量不能超过背包的容量的前提下，使所装入的物品价值取得最大值.
【输入文件】（文件名 bag.in）
第一行一个整数，表示C（1<=C<=10000）,为背包的容量
第二行一个整数，表示N（1<=N<=100）,为物品数量
第三行N 行（每个整数取值范围为[1..100]），每行两个数值，分别表示物品各自的重量，物品的各自的价值
【输出文件】（文件名 bag.out）
只一行，一个整数，表示能取得的最大价值
【输入文件】（文件名 bag.in）
10
4
5 40
1 10
4 25
3 30
【输出结果】（文件名 bag.out）
80