33590번 - Damage per Second 스페셜 저지다국어

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 ≤ n ≤ 200\, 000$, $2 ≤ k ≤ 200\, 000$) — the number of enemies and the number of skill points.

The second line contains $n$ integers $h_i$ ($1 ≤ h_i ≤ 10^{13}$) — the health of the $i$th enemy.

Print two positive integers $x$ and $y$ ($1 ≤ x, y$ and $x + y ≤ 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.