该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小岷每日沉迷在Minecraft。

众所周知在Minecraft里合成一件物品需要若干件材料。

小岷现在想合成一把屠龙宝剑来击败末影龙，目前已知小岷已经收集了合成宝剑所需要的n种不同的材料，第$i$种材料有编号$i$，并且第$i$种材料现有$a_{i}$份。

而如果有$n$份材料，其中每种材料各一份，那么这$n$份材料可以合成一把宝剑。

因为宝剑有耐久度，小岷为了合成出尽可能多的宝剑，他找到了$m$份空白材料，每份空白材料可以变成n种材料的任意一种。然而第$i$种材料最多能由空白材料变$b_{i}$份。

请问小岷最多能合成多少把屠龙宝剑？

输入格式

输入共3行，第一行为两个正整数$n, m$。$n$表示合成宝剑的材料种类，$m$表示空白材料的数量。

第二行为$n$个正整数$a_{1}$,$a_{2}$, ...,$a_{n}$。表示小岷现在拥有第$i$种材料的数量。

第三行为$n$个正整数$b_{1}$,$b_{2}$, ...,$b_{n}$。表示小岷最多能使用空白材料变成第$i$种材料的数量。

输出格式

一行，一个整数表示答案。

数据范围

对于100%的数据，保证$n ≤ 2*10^5$; $a_{i}, b_{i} ≤ 2*n$; $m ≤ n^2$。

样例

4 5
1 2 3 4
5 5 5 5

3

样例解释

这 5 份空白材料中，使用 2 份变成了材料1，使用 1 份变成了材料 2，这样每种材料的份数就变为了 3, 3, 3, 4，可以合成出 3 把宝剑，剩下 2 份空白材料不能再帮助小明合成一把宝剑。