问题描述

详见教材p174问题描述：桐桐有N件货物需要运送到目的地，它们的质量和价值分别记为： 质量：W1,W2,...Wn; 价值：V1,V2,...Vn; 已知某辆货车的最大载货量为x， 并且当天只能运行一趟货物。这辆货车应该运送哪些货物，才能在不超载的前提下使运送的价值最大。

格式

输入

第1行是一个实数，表示货车的最大载货量x(1<x<=100)。 第2行是一个正整数，表示待运送的货物数n(1<n<=20)。 后面n行每行两个用空格隔开的实数，分别表示第1至第n件货物的质量W和价值V。

输出

第1行为被运送货物的总价值（只输出整数部分）。 第2行为按编号大小顺序输出所有被运送货物的编号（当一件都不能运送时，不输出）。

样例

20
4
3.5 4
4 5
5 6.8
6.9 7

22
1 2 3 4

限制

1s, 64MB.