题目描述

现有 N 件货物需要运送到目的地，它们的重量和价值分别记为：

重量：$W_1$，$W_2$，…，$W_n$

价值：$V_1$，$V_2$ ，…，$V_n$

已知某辆货车的最大载货量为 Xk ,并且当天只能运送一趟货物。这辆货车应该运送哪些货物，才能在不超载的前提下使运送的价值最大？

输入格式

第一行为货车的最大载货量 m ；

第二行为待运送的货物数 n (1 <= n <= 20)；

后面 n 行分别为第 1 至第 n 件货物的重量和价值。

输出格式

共有两行：

第一行为被运送货物的总价值（只输出整数部分）；

第二行为所有被运送货物的编号（当一件都不能运送时，不输出）。

样例

16
4
3 4
4 5
5 6
6 7

18
2 3 4

20
4
3.5 4
4 5
5 6.8
6.9 7

22
1 2 3 4

12
3
24 15
18 20
15 30

0