王伯退休后开始养鱼。他一早起来就赶去动物园，发现这个世界的鱼真不少，五光十色、色彩斑斓，大的、小的，什么样的都有。这些鱼实在是太美了，买的人越来越来多， 湖里的鱼越来越少。没有美丽的鱼，那里有美丽的湖？于是动物园不得不规定对于每种鱼，每个人最多只能买一条，并且有些鱼是不能一起买的，因为放在一起他们相互争斗吞食。
王伯想买尽可能多的鱼，但很可惜，它的资金有限，他冥思苦想，不知如何是好。请编程帮他，如果有多个方案能买尽可能多的鱼，选择所花资金最多的一种方案。
[输入]
  第一行：资金m（<=1000）和鱼的种类n（<=30）。以下n行，每行有两个正整数，鱼的编号s(1<=s<=n)和鱼的价格t。接着又有若干行，每行两个整数p,q,当pq都大于0时，表示pq不能共处，当pq均等于0时，表示输入结束。
[输出]
  第一行两个整数，x y,x表示买得鱼的条数，y表示总的花费，以下x行，每行有一个整数，表示所买鱼的编号，编号按升序排列输出。
[样例输入]
170 7
1 70
2 50
3 30
4 40
5 40
6 30
7 50
1 4
1 7
3 4
3 5
5 7
6 3
0 0
[样例输出]
4 170
2
4
6
7