Background

这天，小明在整理他的卡牌。

Description

他一共有 n种卡牌，第i种卡牌上印有正整数数i(i ∈ [1,n])，且第i种卡牌现有$a_i$张。

而如果有n张卡牌，其中每种卡牌各一张，那么这n张卡牌可以被称为一套牌。小明为了凑出尽可能多套牌，拿出了m张空白牌，他可以在上面写上数i，将其当做第i种牌来凑出套牌。然而小明觉得手写的牌不太美观，决定第i种牌最多手写$b_i$张。

Format

Input

输入共3行，第一行为两个正整数n,m。

第二行为n个正整数$a_1,a2,..., a_n$。

第三行为n个正整数$b_1,b_2,... b_n$。

Output

请问小明最多能凑出多少套牌?

Samples

4 5
1 2 3 4
5 5 5 5

3

样例说明

这5张空白牌中，拿2张写1，拿1张写2，这样每种牌的牌数就变为了3,3,3,4，可以凑出3套牌，剩下2张空白牌不能再帮助小明凑出一套。

Limitation

对于30%的数据，保证n ≤2000 ; 对于100%的数据，保证$n≤2×10^5; a_i,b_i≤n; m≤ n^2$。