$O(2^nn)$ 加优化开完O2都能AC。。。

#include<bits/stdc++.h>
using namespace std;
int W,n,t[16],w[16],dp[1<<16];
int main(){
	scanf("%d%d",&W,&n);
	for(int i=0;i<n;i++) scanf("%d%d",&t[i],&w[i]);
	memset(dp,127,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<(1<<n);i++){
		for(int j=i;j;j=i&(j-1)){
			int s=0,ss=0;
			for(int k=0;k<n;k++){
				if((j>>k)&1){
					s=max(s,t[k]);
					ss+=w[k];
					if(ss>W) break;
				}
			}
			if(ss>W) continue;
			dp[i]=min(dp[i],dp[i^j]+s);
		}
	}
	printf("%d",dp[(1<<n)-1]);
	return 0;
}