Description

现有N件货物需要运送到目的地，它们的重量和价值分别记为： 重量：W1，W2，…，Wn 价值：V1，V2 ，…，Vn
已知某辆货车的最大载货量为Xk 并且当天只能运送一趟货物。这辆货车应该运送哪些货物，才能在不超载的前提下使运送的价值最大？

Input

输入文件的第一行为货车的最大载货量，第二行为待运送的货物数n； 后面n行分别为第1至第n件货物的重量和价值。

Output

输出文件共有两行： 第一行为被运送货物的总价值（只输出整数部分）； 第二行为所有被运送货物的编号（当一件都不能运送时，不输出）。

Samples

16
4
3 4
4 5
5 6
6 7

18
2 3 4

12
3
24 15
18 20
15 30

0

Limitation

1s, 1024KiB for each test case.