#include<iostream>
#include<string>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;

int c;//背包容纳的重量
int n;//物品数量
int cw;//当前重量
int cv;//当前价值
int bestv;//当前最优价值
int x[100];
int bestx[100];
struct Object
{
    int id;
    int w;//物品重量
    int v;//物品价值
    double d;//物品的单位价值重量比d=v/w
} Q[100];

bool cmp(Object a,Object b)
{
    if(a.d>b.d)
        return true;
    else
        return false;
}
int Bound(int s)
{
    int cleft=c-cw;//背包剩余容量
    double b=cv;//上界价值

    while(s<=n&&Q[s].w<=cleft)
    {
        cleft-=Q[s].w;
        b+=Q[s].v;
        s++;
    }

    if(s<=n)
    {
        b+=1.0*Q[s].v/Q[s].w*cleft;
    }
    return b;
}
void BackTrack(int s)
{
    if(s>n)
    {
        bestv=cv;
        for(int i=1;i<=n;i++)
            bestx[i]=x[i];
        return ;
    }
    if(cw+Q[s].w<=c)
    {
        x[Q[s].id]=1;
        cw+=Q[s].w;
        cv+=Q[s].v;
        BackTrack(s+1);
        cw-=Q[s].w;
        cv-=Q[s].v;
        x[Q[s].id]=0;
    }
    if(Bound(s+1)>bestv)
    {
        x[Q[s].id]=0;
        BackTrack(s+1);
    }
}

int main()
{
    cout<<"输入物品容纳的重量：";cin>>c;
    cout<<"输入物品数量：";cin>>n;
    cout<<"输入每个物品的重量及价值："<<endl;
    for(int i=1;i<=n;i++)
    {
        cin>>Q[i].w>>Q[i].v;
        Q[i].id=i;
        Q[i].d=1.0*Q[i].v/Q[i].w;
    }
    sort(Q,Q+n,cmp);

    BackTrack(1);

    cout<<"最大总价值："<<bestv<<endl;
    cout<<"选取的物品为：";
    for(int i=1;i<=n;i++)
    {
        if(bestx[i]==1)
            cout<<i<<" ";
    }
    return 0;
}