共用充电器¶

时间限制：0.5 秒。内存限制：128 MiB。参考评测环境与性能。

背景故事¶

一场考试允许使用笔记本电脑，但考生们只有一个可共用的充电器。组织者可以选择充电器的固定功率，希望用最小功率保证所有电脑坚持到考试结束。

有 $n$ 台设备。设备 $i$ 的初始电量为 $a_i$ ，每分钟消耗 $b_i$ .考试持续 $m$ 分钟，编号为 $0,\ldots,m-1$ .

选择一个固定的非负整数功率 $X$ .每分钟开始时，最多选择一台设备充电，使它获得 $X$ 单位电量；随后所有设备各消耗 $b_i$ .只检查每分钟末的电量，所有设备都必须非负，恰好为零也合法。电量没有容量上限，同一设备可在多个不同的分钟充电。

求可行的最小 $X$ .不存在任何可行功率时输出 $-1$ .

第一行包含 n m .第二行包含 $n$ 个整数 $a_i$ .第三行包含 $n$ 个整数 $b_i$ .

输出一行一个整数：最小功率，或 $-1$ .

7 7
75 96 111 18 26 5 67
11 14 16 13 4 1 11

10 10
6461509295841908 38 62 49 89 113 8 7 26 1
4 6 14 6 12 19 11 2 9 1

10 6
5418305720373823 1522295577184932 68 14 9738943766183541 12 28 64942086170874 58 50
13 5 19 10 14 18 6 7 11 17

7 8
6826325183988349 2889182368658500 114922354894933 144 73 6452986168515306 3965505639613541
5 12 19 20 12 15 15

2 2
0 0
1 1

-1

2 5
0 10
0 2

样例5中，两台设备都必须在第0分钟充电，但每分钟只能给一台设备充电，因此无解。样例6中，现有电量已足够，答案为零。

$一台设备的电量变化示例：$a=1,b=2,X=3$ ，在第0、1分钟充电，三分钟末电量依次为 $2,3,1$ .$

一台设备的电量变化示例：$a=1,b=2,X=3$ ，在第0、1分钟充电，三分钟末电量依次为 $2,3,1$ .

$1\le n,m\le5\cdot10^5$ ，$0\le a_i\le10^{16}$ ，$0\le b_i\le10^9$ .共40个测试点，每点占2.5%。