Damage per Second
Description
You just created a new character in your favourite role-playing game and now have to decide how to skill him.
The two skill attributes to be chosen are: damage per hit and hits per second. Damage per hit is the amount of damage you deal with a single hit, while hits per second is the number of hits you can make in one second. Initially, both skill attributes are set at $0$. You have $k$ skill points to distribute as you want; in other words, you can choose the values of the two skills so that they are positive integers with sum at most $k$.
The tutorial of the game (the boring part you want to finish as soon as possible) consists of $n$ monsters to be killed one after the other. The $i$-th monster has $h_i$ health points, i.e., it dies after you have inflicted at least $h_i$ damage.
How can you assign the two skill attributes to minimize the time necessary to kill all the $n$ monsters?
The first line contains two integers $n$ and $k$ ($1\leq n\leq200\,000$, $2\leq k\leq200\,000$) — the number of enemies and the number of skill points.
The second line contains $n$ integers $h_i$ ($1\leq h_i\leq10^{13}$) — the health of the $i$th enemy.
Print two positive integers $x$ and $y$ ($1\le x, y$ and $x+y\le k$) — the number of skill points you want to invest in damage per hit and hits per second. If there are multiple optimal solutions, print any of them.
Input
The first line contains two integers $n$ and $k$ ($1\leq n\leq200\,000$, $2\leq k\leq200\,000$) — the number of enemies and the number of skill points.
The second line contains $n$ integers $h_i$ ($1\leq h_i\leq10^{13}$) — the health of the $i$th enemy.
Output
Print two positive integers $x$ and $y$ ($1\le x, y$ and $x+y\le k$) — the number of skill points you want to invest in damage per hit and hits per second. If there are multiple optimal solutions, print any of them.
1 7
14
4 9
1 2 3 4
5 13
3 4 5 6 7
3 4
4 5
7 6
Note
In the first sample, there is only one monster and you have $7$ skill points to distribute. If you make $3$ damage per hit, you will need $5$ hits to kill it. If you do $4$ hits per second, you will need $1.25$ seconds to beat the monster. There is no way to beat the monster faster than this.
In the second sample, you will need one hit for each monster and a total time of $0.8$ seconds if you distribute $4$ skill points on damage per hit and the remaining $5$ points on hits per second.