Description

zty特别喜欢 期末考试 。

2077年的期末考试，已经可以自带电脑了。zty叫上班上的n位同学，带着电脑来到基础实验楼参加考试。但是，他们都忘记带充电器了。

考试总共持续m分钟 ，第i位同学的电脑在考试开始时有$a_i$的电量 ，每分钟会消耗$b_i$的电量。

为了让大家顺利完成考试，即所有人的电量在考试过程中的每一分钟的结尾（第0分钟的结尾，第1分钟的结尾,...，第m-1分钟的结尾）均大于等于 0 。zty决定购买一个每分钟充电量为x的超级充电器，其中x一定为非负整数。

zty仅能在每一分钟开始时给至多一位同学的电脑插上充电器，这台电脑在这一分钟结尾时消耗的电量为 $b_i-x$，如果消耗的电量为负，则表示电脑的电量增加。我们认为电量无上限。

zty想知道，是否存在能够让大家顺利完成考试的充电器；如果存在，那么最小的x是多少？

Format

Input

第一行两个正整数n，m，分别表示同学的数量和考试持续的时间。

第2行n个非负整数，其中第i个非负整数$a_i$表示第i位同学电脑的初始电量。

第3行n个非负整数，其中第i个非负整数$b_i$表示第i位同学电脑每分钟消耗的电量

Output

如果存在满足条件的电池，输出一个非负整数，表示其最小电量。否则，输出“-1”（不含引号）。

Samples

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

73

3 3
1024 1024 1024
0 0 0

0

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

91

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

96

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

6

Limitation

本题共有40 个测试点 。

对于测试点 1-12 ，$1<=n, m <=50$; $0 <= a_i<=10 ^{16}$; $0 <= b_i <=5$

对于测试点 13-20 ，$1 <=n, m <= 200$; $0 <=a_i <=10^{16}$ ; $0 <=b_i <= 20$

对于测试点 21-28，$1 <=n, m <= 200$; $0 <= a_i <=10 ^{16}$ ; $0 <=b_i~ <= 10^9$

对于测试点 29-36，$1 <=n, m <= 5*10 ^4$ ; $0 <=a_i <=10 ^{16}$ ; $0 <=b_i <= 10^9$

对于测试点 1-40，$1 <=n, m <= 5*10 ^5$; $0 <= a_i <=10 ^{16}$; $0 <=b_i <= 10^9$