题目描述

Aki 想制作饼干。做出 1 块饼干需要用到 n 种原料，其中第 i 种原料需要 a_i 克。

Aki 现在手上有第 i 种原料 b_i 克，另外还有 k 克魔法粉。

每 1 克魔法粉都可以在制作前转化成任意一种原料的 1 克， 但使用的魔法粉不能超过k克。

请你求出：Aki 最多能制作多少块饼干。

输入格式

第一行两个整数 n,k，满足 1≤ n≤ 10⁵，1≤ k≤ 10⁹。

第二行 n 个整数 a₁,a₂,…,a_n，表示制作 1 块饼干时各原料所需克数，满足 1≤ a_i≤ 10⁹。

第三行 n 个整数 b₁,b₂,…,b_n，表示当前持有的各原料克数，满足 1≤ b_i≤ 10⁹。

输出格式

输出一个整数，表示最多能制作的饼干数量。

1 1000000000
1
1000000000

2000000000

3 1
2 1 4
11 3 16

4

Hint

注意： 本题代码化过程中，留意变量相乘结果是否会爆longlong，其中longlong的上限 ≈ $4 \times 10^{18}$