采药
#include<bits/stdc++.h>
using namespace std;
int t,m,w[105],v[105],f[105][1005];
int main()
{
cin>>t>>m;
for(int i=1; i<=m; i++)
cin>>w[i]>>v[i];
for(int i=1; i<=m; i++)
{
for(int j=t; j>=0; j--)
{
if(j>=w[i])
f[i][j]=max(f[i-1][j-w[i]]+v[i],f[i-1][j]);
else f[i][j]=f[i-1][j];
}
}
cout<<f[m][t];
}
// http://www.jzoj.cn/problem.php?id=1746
// 30%
# include <bits/stdc++.h>
using namespace std;
int n,a[101];
int W,w[101],v[101],maxv;
int tw,tv;
int rest(int dep){
int s=0;
for(int i=dep;i<=n;i++) s+=v[i];
return s;
}
void dfs(int dep){
if(dep>n) //方案处理，计算这个方案的总重量和总价值
{
if(tv>maxv) maxv=tv;
}
else{
for(int i=0;i<=1;i++){
a[dep]=1-i;
if(tw+a[dep]*w[dep]<=W && tv+a[dep]*v[dep]+rest(dep+1)>maxv ){
tw+=a[dep]*w[dep];
tv+=a[dep]*v[dep];
dfs(dep+1);
tw-=a[dep]*w[dep];
tv-=a[dep]*v[dep];
}
}
}
}
int main(){
cin>>W>>n;
for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
dfs(1);
cout<<maxv<<endl;
return 0 ;
}