#include<bits/stdc++.h>
using namespace std;
int dp[35][205];//dp[i][j]前i个物品，占用j个单位空间
int n,m;
int v[35];//第i件物品的体积
int w[35];//第i件物品的价值
vector <int> e[35][205];//前i个数，总共j空间，塞了哪些数
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)//考虑第i件物品选不选
for(int j=1;j<=m;j++)
{
if(j-v[i]>=0)
{
//dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
if(dp[i-1][j-v[i]]+w[i]>=dp[i-1][j])
{
dp[i][j]=dp[i-1][j-v[i]]+w[i];
//把e[i-1][j-v[i]]的所有点都压入e[i][j]
for(int k=0;k<e[i-1][j-v[i]].size();k++)
e[i][j].push_back(e[i-1][j-v[i]][k]);
e[i][j].push_back(i);
}
else
{
for(int k=0;k<e[i-1][j].size();k++)
e[i][j].push_back(e[i-1][j][k]);
dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
}
}
else
{
for(int k=0;k<e[i-1][j].size();k++)
e[i][j].push_back(e[i-1][j][k]);
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][m]<<endl;
cout<<e[n][m].size()<<endl;
for(int i=0;i<e[n][m].size();i++)
cout<<e[n][m][i]<<" ";
return 0;
}

赶在老师前面……