题目描述

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

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

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

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

输入格式

第一行是一个实数，表示货车的最大载货量 x ( 1 < x <= 100)。

第二行是一个正整数，表示待运送的货物数 n ( 1 < n ≤ 20 )。

后面 n 行每行两个用空格隔开的实数，分别表示第 1 至第 n 件货物的重量 W 和价值 V。

输出格式

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

第二行为按编号大小顺序输出所有被运送货物的编号(当一件都不能运送时，不输出)。

样例

20
4
3.5 4
4 5
5 6.8
6.9 7

22
1 2 3 4