> 不优化貌似会tle 数据范围好像也不太对贡献了几个re 加一个判断条件就好
> 
> #include<string.h>
> #include<stdio.h>
> int s,n,max, a[111],x,y,z, i,k, j,v[100005];
> int main() {
> 	while (scanf("%d", &s) != EOF)
> 	{
> 		memset(v, 0, sizeof(v)); v[0] = 1; z = 1;
> 		scanf("%d",&n);
> 		for (i = 1; i <= n; i++)
> 		{
> 			scanf("%d%d", &x, &y);
> 			k = 1;
> 			while (x>0)
> 			{if(x>=k) a[z++] = k*y, x = x - k, k = k<<1;
> 			else {
> 				a[z++] = x*y; break;
> 	}}}
> 		for (i = 1; i < z; i++)
> 			for (j = s; j >= 0; j--)
> 				if (v[j]&& j + a[i] <= s)
> 				 v[j + a[i]] = 1;
> 		for (i = s; i!=0; i--)
> 			if (v[i]) break;
> 		printf("%d\n",i);
> 	}}