Problem #2711 - ECNU Online Judge

单点时限: 5.0 sec

内存限制: 256 MB

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 $a_{1}, a_{2}, \dots, a_{n}$ 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 ( $0 \leq n \leq 30, 1 \leq m \leq 30$ ). The second line contains $n$ integer numbers ranging from $1$ to $10^{9}$ ― 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.

样例

Input

3 2
2 3 9

Output

1
7

10 人解决，26 人已尝试。

13 份提交通过，共有 85 份提交。

7.4 EMB 奖励。

创建: 16 年，5 月前.

修改: 7 年，2 月前.

最后提交: 7 年前.

来源: NEERC 2008

construction greedy

2711. Key to Success

输入格式

输出格式

样例

服务

开源

关于我们