311201: CF1949E. Damage per Second

E. Damage per Secondtime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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?

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.

ExamplesInput

1 7
14

Output

3 4

Input

4 9
1 2 3 4

Output

4 5

Input

5 13
3 4 5 6 7

Output

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.

题目大意：
你在一个角色扮演游戏中创建了一个新角色，并需要决定如何分配技能点。你可以选择两个技能属性：每次攻击的伤害（damage per hit）和每秒攻击次数（hits per second）。最初，这两个技能属性都设定为0。你有k个技能点可以任意分配；换句话说，你可以选择两个技能的值，使得它们是正整数且总和最多为k。

游戏教程（你希望尽快完成的枯燥部分）包括n个需要逐个击败的怪物。第i个怪物有h_i个生命值，即你在对其造成至少h_i点伤害后它才会死亡。

你如何分配这两个技能属性以最小化击败所有n个怪物所需的时间？

输入数据格式：
第一行包含两个整数n和k（1≤n≤200,000，2≤k≤200,000）——敌人的数量和技能点的数量。
第二行包含n个整数h_i（1≤h_i≤10^13）——第i个敌人的生命值。

输出数据格式：
打印两个正整数x和y（1≤x,y且x+y≤k）——你想要投资于每次攻击的伤害和每秒攻击次数的技能点数。如果有多个最优解，请输出其中任何一个。

示例：
输入
1 7
14
输出
3 4

输入
4 9
1 2 3 4
输出
4 5

输入
5 13
3 4 5 6 7
输出
7 6

注意：
在第一个示例中，只有一个怪物，你有7个技能点可以分配。如果你每次攻击造成3点伤害，你将需要5次攻击来杀死它。如果你每秒攻击4次，你将需要1.25秒来击败怪物。没有比这更快击败怪物的办法。

在第二个示例中，如果你将4个技能点分配给每次攻击的伤害，剩下的5点分配给每秒攻击次数，你将需要对每个怪物进行一次攻击，总时间为0.8秒。题目大意： 你在一个角色扮演游戏中创建了一个新角色，并需要决定如何分配技能点。你可以选择两个技能属性：每次攻击的伤害（damage per hit）和每秒攻击次数（hits per second）。最初，这两个技能属性都设定为0。你有k个技能点可以任意分配；换句话说，你可以选择两个技能的值，使得它们是正整数且总和最多为k。 游戏教程（你希望尽快完成的枯燥部分）包括n个需要逐个击败的怪物。第i个怪物有h_i个生命值，即你在对其造成至少h_i点伤害后它才会死亡。 你如何分配这两个技能属性以最小化击败所有n个怪物所需的时间？ 输入数据格式： 第一行包含两个整数n和k（1≤n≤200,000，2≤k≤200,000）——敌人的数量和技能点的数量。 第二行包含n个整数h_i（1≤h_i≤10^13）——第i个敌人的生命值。 输出数据格式： 打印两个正整数x和y（1≤x,y且x+y≤k）——你想要投资于每次攻击的伤害和每秒攻击次数的技能点数。如果有多个最优解，请输出其中任何一个。 示例： 输入 1 7 14 输出 3 4 输入 4 9 1 2 3 4 输出 4 5 输入 5 13 3 4 5 6 7 输出 7 6 注意： 在第一个示例中，只有一个怪物，你有7个技能点可以分配。如果你每次攻击造成3点伤害，你将需要5次攻击来杀死它。如果你每秒攻击4次，你将需要1.25秒来击败怪物。没有比这更快击败怪物的办法。 在第二个示例中，如果你将4个技能点分配给每次攻击的伤害，剩下的5点分配给每秒攻击次数，你将需要对每个怪物进行一次攻击，总时间为0.8秒。