$Description$Description

有一堆东西
有代价和不满意值
问怎样在时间（总范围）内使得不满意值最小

$Input$Input

输入文件的第一行只有一个数字 k。
第二行只有一个数字 n。
接下来 n 行，每行两个数字，分别是 ti 和 pi，两个数字之间用一个空格分开。

$Output$Output

输出文件 homework.out 仅包含一行，是一个数字，代表了光光最少受到的批评。

$Sample$Sample $Input$Input

5
3
2 6
1 3
4 7

$Sample$Sample $Output$Output

6 

$Hint$Hint

【数据范围】
100%的数据中， k<=100000， ti<=10000， pi<=10000；
30%的数据中， n<=20；
100%的数据中， n<=500。

$Train$Train $of$of $Thought$Thought

01背包（最后用总范围-求出的值）

$Code$Code

#include<cstdio>
#include<iostream>
using namespace std;
int k,n,T[1005],P[1005],ans,f[100005];
int main()
{
	//freopen("homework.in","r",stdin);
	//freopen("homework.out","w",stdout);
	scanf("%d%d",&k,&n);
	for (int i=1; i<=n; ++i)
	{
		scanf("%d%d",&T[i],&P[i]);
		ans+=P[i];
	}
	for (int i=1; i<=n; ++i)
	{
		for (int j=k; j>=T[i]; --j)
		{
			f[j]=max(f[j],f[j-1]);
			f[j]=max(f[j],f[j-T[i]]+P[i]);
		}
	}
	printf("%d",ans-f[k]);
	return 0;
}