题目描述 Description
Txx是一个成绩很差的人，考试便成了他的噩梦。于是他常在考试时睡觉以打发时间。今天他又要面临一次考试，为了保证有充足的睡眠，他决定只做k分钟题目。这次测试有n道题，第i题的得分是pi分，需要耗费ti分钟解决（将要完成也得不到分）。
请你算出他最少扣多少分（总分是所有题目分值的总和）。
输入描述 Input Description
第一行k
第二行n
第三行到第n+2行每行两个数：ti和pi
输出描述 Output Description
Txx最少的扣分
样例输入 Sample Input
5
3
2 6
1 3
4 7
样例输出 Sample Output
6
数据范围及提示 Data Size & Hint
100%的数据中，k<=100000，ti<=10000，pi<=10000；
30%的数据中，n<=20；
100%的数据中，n<=500
大水题i
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 int n,k,tot; 7 int t[10015],p[10015],f[100555]; 8 9 int main() 10 { 11 scanf("%d%d",&k,&n); 12 for(int i=1;i<=n;i++) 13 scanf("%d%d",&t[i],&p[i]),tot+=p[i]; 14 for(int i=1;i<=n;i++) 15 for(int j=k;j>=t[i];j--) 16 f[j]=max(f[j],f[j-t[i]]+p[i]); 17 printf("%d",tot-f[k]); 18 return 0; 19 }