Berland SU 今天为其学生举办了另一场训练比赛。 $$$n$$$学生来了,每个人都带着他的笔记本电脑。然而,结果发现大家都忘记带充电器了!
让学生从 $$$1$$$ 到 $$$n$$$ 进行编号。第 $$$i$$$ 学生的笔记本电脑在比赛开始时已充电 $$$a_i$$$,并且每分钟使用 $$$b_i$$$ 充电(即,如果笔记本电脑在某分钟开始时充电 $$$c$$$,则在下一分钟开始时充电为 $$$c - b_i$$$)。整个比赛持续 $$$k$$$ 分钟。
Polycarp(Berland SU的教练)决定购买一个充电器,以便所有学生都能顺利完成比赛。他在比赛开始的同时购买了充电器。
Polycarp可以选择购买具有任何非负(零或正)整数功率输出的充电器。功率输出在购买前已选择,购买后无法更改。令所选功率输出为$$$x$$$。在每分钟开始时(从比赛开始的那一分钟到比赛的最后一分钟),他可以将充电器插入任何学生的笔记本电脑并使用它一段整数分钟。如果笔记本电脑每分钟使用 $$$b_i$$$ 充电,则在插入充电器时,它将变为每分钟 $$$b_i - x$$$。负电量使用率意味着笔记本电脑的电量正在增加。任何笔记本电脑的电量都不受限制,它可以变得无限大。该充电器最多只能同时插入一台笔记本电脑。
如果笔记本电脑的电量在某一分钟开始时从未低于零(从比赛开始的那一分钟到比赛的最后一分钟,允许零电量),则该学生成功完成比赛。比赛结束时笔记本电脑的电量并不重要。
帮助 Polycarp 确定充电器应具有的最小可能功率输出,以便所有学生都能成功完成比赛。如果不存在此类充电器,请同时报告。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — 学生数量(以及相应的笔记本电脑)和比赛持续时间(以分钟为单位)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — 每个学生笔记本电脑的初始费用。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^7$$$) — 每个学生笔记本电脑的电量使用情况。
输出
打印一个非负整数 - 充电器应具有的最小可能功率输出,以便所有学生都能成功完成比赛。
如果不存在这样的充电器,则打印-1。
示例
输入 #1
2 4 3 2 4 2
输出 #1
5
输入 #2
1 5 4 2
输出 #2
1
输入 #3
1 6 4 2
输出 #3
2
输入#4
2 2 2 10 3 15
输出#4
-1
注意
让我们看一下第一个例子中笔记本电脑在每分钟开始时的状态,充电器的功率为$$$5$$$:
1.充电:$$$[3, 2]$$$,将充电器插入笔记本电脑1;
2.充电:$$$[3 - 4 + 5, 2 - 2] = [4, 0]$$$,将充电器插入笔记本电脑2;
3.充电:$$$[4 - 4, 0 - 2 + 5] = [0, 3]$$$,将充电器插入笔记本电脑1;
4. 费用:$$$[0 - 4 + 5, 3 - 2] = [1, 1]$$$。
比赛在第四分钟后结束。
但是,让我们考虑一下电源 $$$4$$$ 的充电器:
1.充电:$$$[3, 2]$$$,将充电器插入笔记本电脑1;
2.充电:$$$[3 - 4 + 4, 2 - 2] = [3, 0]$$$,将充电器插入笔记本电脑2;
3. 电荷:$$$[3 - 4, 0 - 2 + 4] = [-1, 2]$$$,第一台笔记本电脑带负电荷,因此,第一个学生没有完成比赛。
在第四个示例中,无论充电器的功率有多大,其中一名学生都无法完成比赛。