题目描述

小Z在拼豆店拼豆。

他的板子上的 $n$ 列已经拼好了一些豆子，每一列已拼好的高度为 $a_i$。一个一个拼实在太慢了，所以小Z准备上科技：电动拼豆笔！

电动拼豆笔每次操作可以一次性将连续的若干列的高度都 $+1$，不过他使用的不熟练，最多只能使用 $k$ 次电动笔。

因为怕影响到已经拼好的部分，每一列能承受的操作次数上限为 $c_i$。

小Z想知道通过合理的操作之后，最低的那一列的高度最大是多少。

输入格式

第一行：两个整数 $n, k$，表示列的总数和最多使用电动笔的次数。

第二行：$n$ 个整数，表示初始每列豆子的高度。

第三行：$n$ 个整数，表示每列可承受的最多操作次数。

输出格式

通过合理的操作之后，最低的那一列的高度最大值。

输入输出样例

5 5
10 8 12 6 9
3 2 4 4 2

10

样例 $\tt \#1$说明

一种方案是

• 第二列操作 $1$ 次，变为 $[10,9,12,6,9]$
• 第四列操作 $2$ 次，变为 $[10,9,12,8,9]$
• $2\sim 4$ 列操作 $1$ 次，变为 $[10,10,13,9,9]$
• $4\sim 5$ 列操作 $1$ 次，变为 $[10,10,13,10,10]$

最低的高度是 $10$。

数据范围

对全部数据，保证 $1 \le k,a[i],c[i] \le10^9$。