Problem H
Robbers are Often Robbed
Mario finds himself in a wealthy neighborhood. There are $N$ homes on a street each with $S_ i$ stars where $i \in [1, N]$. He is given $K$ burlap sacks with an infinite capacity to hold stolen stars. He can take as many or as few stars as he’d like from each house. However, a star from one home does not get along with a star from another home. As a result, stars from different homes can’t be placed in the same knapsack. However, Mario can split the stars from the one house across multiple sacks. Mario can also leave a sack empty if he deems it necessary.
Once Mario has completed his robbery, he will encounter Bowser who will steal exactly half of his knapsacks. Bowser will of course steal the sacks with the most stars. Knowing this, Mario has two objectives. His first priority is to maximize the amount of stars that he has at the end. After maximizing this value $M$, his second priority is to ensure that Bowser steals the minimum amount of stars across all possible robbing outcomes that leave Mario with $M$ stars.
For example, in the first sample case, Mario can steal $10$ stars from the houses $2$, $6$, and $9$, while stealing $9$ stars from house $8$. Bowser will steal the largest two sacks giving him $20$ stars while Mario will keep $19$ of the stars. Note that $19$ stars is the largest amount of stars that Mario could have possibly acquired, while $20$ is the minimum amount of stars that Bowser will steal across all outcomes where Mario gets $19$ stars.
However, in the second sample case, Mario will split the $30$ stars from house $2$ across three of his knapsacks evenly, and then steal $10$ of the stars from house $3$ in his fourth knapsack. Bowser will steal $20$ of these stars, leaving Mario with $20$ stars as well.
Output two numbers representing the maximum stars Mario can rob and the minimum number of stars he must give Bowser.
Input
The first line contains two space-separated integers:
$N$ and $K$ $(1
\leq N,K \leq 1\, 000)$ . It is guaranteed that
$K$ is even.
The next line will contain $N$ numbers $S_ i$ $(0 \leq S_ i \leq 1\, 000)$, each
representing the number of stars at each house.
Output
Output one line containing two numbers representing the maximum stars Mario can rob and the minimum number of stars he must give Bowser in that order.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 4 3 12 4 6 1 10 8 9 18 0 |
19 20 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 4 9 30 11 |
20 20 |
