Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS08AKP - Another Knapsack Problem

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 < mi < S and its value 0 <= vi < 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, Vp - V}, where Vp 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:kuszi
Date:2009-05-31
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CLOJURE NODEJS PERL6 VB.NET

hide comments
2015-08-20 14:47:01 kuszi
This is an optimisation problem. There is no the only one correct answer - there are better and worse ones.
2015-08-13 20:23:38
is the test case correct? the max value should be 17 for index 0,1,3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.