| Author: | ACM ICPC 2008-2009, NEERC, Northern Subregional Contest | Time limit: | 3 sec | |
| Input file: | key.in | Memory limit: | 256 Mb | |
| Output file: | key.out |
The organizers of the TV Show "Key to Success" are preparing a set of prizes for the winner of the game. If the score of the winner is X, she must choose prizes with a total value of exactly X dollars.
The organizers have a couple of spare prizes from the previous competitions that have values a1, a2, … , an dollars, respectively. Unfortunately they don't know what the score of the winner will be. So the organizers decided to buy m more prizes in order to maximize the minimal integer score that the winner of the show wouldn't be able to collect prizes for.
For example, if they already have prizes for 2, 3 and 9 dollars, and they want to buy 2 prizes, they should buy prizes for 1 and 7 dollars. Then the winner of the show would be able to collect prizes for any score from 1 to 22.
The first line of the input file contains two integer numbers: n and m — the number of prizes the organizers have and the number of prizes they are ready to buy. The second line contains n integer numbers ranging from 1 to 109 — the values of the prizes organizers have.
Output m integer numbers — the values of the prizes the show organizers should buy. Output numbers in non-decreasing order. If there are several optimal solutions, output any one.
0 ≤ n ≤ 30, 1 ≤ m ≤ 30.
| No. | Input file (key.in) |
Output file (key.out) |
|---|---|---|
| 1 |
|
|