王伯退休后开始养鱼。他一早起来就赶去动物公园，发现这个世界的鱼真不少，五光十色、色彩斑斓，大的、小的，什么都有。这些鱼实在是太美了，买的人越来越多，湖里的鱼越来越少。没有美丽的鱼，哪里有美丽的湖？于是动物公园不得不规定，对于 每种鱼，每个人最多只能买一条。并且有些鱼是不能一起买的，因为它们之间会互相争斗吞食。王伯想买尽可能多的鱼，但很可惜，他的资金有限。他冥思苦想，不知如何是好。请编程写一个程序帮助他。如果有多个方案都能买尽可能多的鱼，选择所花资金最多的一个。

Input

输入数据的第一行为两个正整数M（M<=1000），N（N<=30），分别表示王伯的资金和鱼的种类。以下N行，每行有两个正整数S（1<=S<=N），T，分别表示某种鱼的编号以及该鱼的价格。接着，每行有两个整数P，Q。当P，Q均大于0时，表示P，Q不能共处；当P，Q均等于0时，表示输入的结束。

Output

输出数据的第一行为两个正整数X，Y，分别表示所买鱼的条数和总花费。以下X行，每行有一个正整数，表示所买鱼的编号。编号按升序排列输出。如果题目有多个解，只需输出其中的一个。

Sample Input

170 7
1 70
2 50
3 30
4 40
5 40
6 30
7 20
1 4
1 7
3 4
3 5
5 7
6 7
0 0

Sample Output

4 160
2
4
5
6

//一下是本人写的一段不完全实现的代码，不能找到最优解??????????!!!!!!!!!

#include<iostream>
using namespace std;
int main()
{
    int M,N,st[30][2],pq[50][2];
    int i,j;
    for(i=0;i<30;i++)
    {
        st[i][0]=0;
        st[i][1]=0;
    }
    cin>>M>>N;
    int s=0;
    for(s=0;s<N;s++)
    {
        cin>>st[s][0]>>st[s][1];
        while(st[s][0]<1 || st[s][0]>N)
        {
            cin>>st[s][0]>>st[s][1];
        }
    }
    cin>>pq[0][0]>>pq[0][1];
    while(pq[s][0]<0 || pq[s][1]<0)
    {
        cin>>pq[s][0]>>pq[s][1];
    }
    s=0;
    while(pq[s][0] != 0 || pq[s][1] != 0)
    {
        s++;
        cin>>pq[s][0]>>pq[s][1];
        while(pq[s][0]<0 || pq[s][1]<0)
        {
            cin>>pq[s][0]>>pq[s][1];
        }
    }
   
    for(i=0;i<N-1;i++)
    {
        for(j=i+1;j<N;j++)
        {
            if(st[i][1]<st[j][1])
            {
                s=st[i][0];
                st[i][0]=st[j][0];
                st[j][0]=s;

                s=st[i][1];
                st[i][1]=st[j][1];
                st[j][1]=s;
            }
        }
    }
   
    s=0;
    i=0;
    int answer[30]={0},count=0,money=M;
    int k,flag=0;
    while(M>0)
    {
        flag=0;
        if(M>=st[s][1])
        {
            for(i=0;pq[i][0]!=0 && pq[i][1]!=0;i++)
            {
                if(st[s][1]==pq[i][0])
                {
                    for(k=0;answer[k]>0;k++)
                    {
                        if(pq[i][1]==answer[k])
                        {
                            flag=1;
                            break;
                        }
                    }
                }
                if(st[s][1]==pq[i][1])
                {
                    for(k=0;answer[k]>0;k++)
                    {
                        if(pq[i][0]==answer[k])
                        {
                            flag=1;
                            break;
                        }
                    }
                }
                if(flag==1)
                    break;
            }
            if(flag==0)
            {
                answer[count]=st[s][0];
                count++;
                M=M-st[s][1];
            }
        }
        s++;
        if(st[s][0]==0 || s==29)
            break;
    }

    money=money-M;
    for(i=0;i<count-1;i++)
    {
        for(j=i+1;j<count;j++)
        {
            if(answer[i]>answer[j])
            {
                s=answer[i];
                answer[i]=answer[j];
                answer[j]=s;
            }
        }
    }
    cout<<count<<" "<<money<<endl;
    for(i=0;i<count;i++)
    {
        cout<<answer[i]<<endl;
    }
    return 0;
}