#7. 期末考试

期末考试

Description

zty特别喜欢 期末考试

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

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

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

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

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

Format

Input

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

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

第3行n个非负整数,其中第i个非负整数bib_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-121<=n,m<=501<=n, m <=50; 0<=ai<=10160 <= a_i<=10 ^{16}; 0<=bi<=50 <= b_i <=5

对于测试点 13-201<=n,m<=2001 <=n, m <= 200; 0<=ai<=10160 <=a_i <=10^{16} ; 0<=bi<=200 <=b_i <= 20

对于测试点 21-281<=n,m<=200 1 <=n, m <= 200; 0<=ai<=10160 <= a_i <=10 ^{16} ; 0<=bi <=1090 <=b_i~ <= 10^9

对于测试点 29-361<=n,m<=5104 1 <=n, m <= 5*10 ^4 ; 0<=ai<=10160 <=a_i <=10 ^{16} ; 0<=bi<=1090 <=b_i <= 10^9

对于测试点 1-401<=n,m<=5105 1 <=n, m <= 5*10 ^5; 0<=ai<=10160 <= a_i <=10 ^{16}; 0<=bi<=1090 <=b_i <= 10^9