题目描述

有一个城市自西向东有一条很长的道路，道路边上有n个设施，以最西端为坐标0点，第i个设施位于坐标$a_i$米处。

现在市政府决定对这n个设施进行安全检查，第i个设施有$b_i$个检查项目需要进行。进行检查的工人有k名，他们从道路最西端出发，每名工人每分钟可以进行以下两种行动之一：

（1）向东移动1米。

（2）完成当前所处的设施的1项检查项目。

要把所有设施的所有检查项目全部完成，至少需要多长时间？

输入格式

第1行，2个正整数n,k

第2行，n个正整数$a_{1}$,$a_{2}$,⋯,$a_n$

第3行，n个正整数$b_{1}$,$b_{2}$,⋯,$b_n$

输出格式

完成所有设施的所有检查需要的最短时间

样例输入

3 3
1 3 4
4 2 4

样例输出

7

提示

有10%数据$k=1$

另有10%数据$k=2$

100%数据，$1\le n\le 10^{5}$；$1\le k\le 10^{9}$；$1\le a_i,b_i\le 10^{9}$；$a_i\lt a_i+1$。

第1分钟：3人移动到坐标1。

第2分钟：3人分别完成设施1的1项检查。此时设施1完成了3个检查项目。

第3分钟：第1、2人移动到坐标2，第3人完成设施1的1项检查。至此1号设施的4项检查全部完成。

第4分钟：第1、2人移动到坐标3，第3人移动到坐标2。

第5分钟：第1、2人移动到坐标4，第3人移动到坐标3。

第6分钟：第1、2人分别完成设施3的1项检查，第3人完成设施2的1项检查。此时设施3完成了2个检查项目，设施2完成了1个检查项目。

第7分钟：第1、2人分别完成设施3的1项检查，第3人完成设施2的1项检查。至此所有设施的所有检查项目全部完成。

3 3
1 3 4
4 2 4

7

3 3 
1 3 4 
4 2 4

7

6 2
1 4 5 6 11 15
12 5 9 8 10 4

35