Another Knapsack Problem

Problem code: HS08AKP

Given 1 < n < 100 000 items, select some of them in such a way that the total weight of the selected items is at most S (1 < S < 1 000 000 000). For each item i you are given its weight 0 < m_i < S and its value 0 <= v_i < 1000. The larger the value of selected items, the better. Can you obtain the optimal solution?

Input

First two positive integers, S and n. Then n lines follows. In the i-th line there are exactly two numbers, denoting the mass and value of the i-th item, respectively.

Output

In the first line output k - the number of items to be taken. Next, output their numbers with respect to the order given by the input.

Scoring

The score awarded to your program for a given test is computed as max{0, V_p - V}, where V_p is your program score, and V is a reference value (the result obtained by greedy approximation algorithm minus 10). The overall score of the program is the sum of scores obtained for the correctly solved tests.

The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Example

Input:
4 5
1 8
2 4
3 0
1 5
2 3

Output:
2
1 4 

Scoring:
As V=7, the above solution scores max{0, 13 - 7} = 6 points.

Input data sizes

Approximate test data sizes are given below.

 t     n       l 
 1    72100    2s
 2    40000    2s
 3    4000     2s
 4    94100    2s
 5    9000     2s

 t - testcase number
 n - the number of items
 l - time limit 

Please note

Submissions will be visible to the submitting contestant, only, and tested on the full set of test cases.

---

Added by:	Łukasz Kuszner
Date:	2009-05-31
Time limit:	2s
Source limit:	50000B
Languages:	SED C99 strict C++ 4.0.0-8 C++ 4.3.2 TCL SCALA NEM PHP SCM guile LISP sbcl LISP clisp ERL TECS TEXT DOC PDF PS PERL 6 JS