0097. FAQ

Input file name: faq.in
Output file name: faq.out
Time limit: 2 s
Memory limit: 64 megabytes

The DogsSoft is creating a Frequently Asked Questions server. They have selected a computer but they have decided to save money on buying a harddisk so it is very small. Now they try to arrange the questions. But they have encountered a huge problem. The total size of questions exceeds the harddisk size! How to select the best ones? They have decided to use a brute force solution. The server will contain arbitrary set of questions giving maximal possible total size. So you task is to select such subset from a given set of questions.

Input file

First line of the input file contains a total size of harddisk in Kbytes S (1 ≤ S ≤ 106) and the number of the questions for the FAQ n (1 ≤ n ≤ 239). The next n lines contain the size, in Kbytes, of i-th question explanation with sample programs, pictures and other stuff – si (1 ≤ si ≤ 106).

Output file

The first line contains the maximal total size of questions which should be written to the disk. The second line contains number of the possible questions selected in ascending order, terminated by zero.

Examples:

faq.infaq.out
1000000 3 239000 717000 666000956000 1 2 0


Source: Petrozavodsk Summer 2003. Opening Contest, Friday, August 22
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version