题目描述

小华打算用 n 种（编号为 1 到 n ）材料组装玩具。其中第 i 种材料的数量为 $X_i$ 个。组装一个玩具需要第 i 种材料 $Y_i$ 个。小华另外有 m 个万能材料，每个万能材料可以作为 n 种材料中的任意一个材料使用。

请编程计算小华最多可以组装多少个玩具？

输入格式

共 3 行：

第 1 行两个整数 n 和 m ，分别表示小华有 n 种材料和 m 个万能材料。

第 2 行 n 个正整数，其中第 i 个整数 $X_i$ 表示小华第 i 种材料有 $X_i$ 个。

第 3 行 n 个正整数，其中第 i 个整数 $Y_i$ 表示小华组装一个玩具需要第 i 种材料 $Y_i$ 个。

数据范围

50% 的测试点输入数据保证 1 ≤ n ≤ 1000 , 1 ≤ m ≤ ${10}^4$ , 1 ≤ $X_i , Y_i$ ≤ ${10}^4$ 。

100% 的测试点输入数据保证 1 ≤ n ≤ 100000 , 1 ≤ m ≤ ${10}^9$ , 1 ≤ $X_i, Y_i$ ≤ ${10}^9$。

输出格式

一个整数，表示小华最多可以组装多少个玩具。

样例

1 1
1
1

2

3 1
13 7 20
3 2 5

4

样例解释

样例 1 解释：输入中小华只有 1 个编号为 1 的材料，另外还有 1 个万能材料。组装一个玩具需要编号为 1 的材料 1 个。所以可以用 1 个编号为 1 的材料和 1 个万能材料分别组装 1 个玩具，共可以组装 2 个玩具。