Background

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

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

Input

输入文件 toy.in：输入从文件中读取，输入共 3 行。

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

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

Output

输出文件 toy.out：结果输出到文件中，输出共 1 行。

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

Samples

1 1
1
1

2

3 1
1 1 1
10 10 10

0

3 1
13 7 20
3 2 5

4

2 2
3 3
2 2

2

Limitation

【样例1解释】

输入中小华只有1个编号为1的材料，另外还有1个万能材料。组装一个玩具需要编号

为1的材料1个。所以可以用1个编号为1的材料和1个万能材料分别组装1个玩具，共可

以组装2个玩具。

【样例2解释】

输入中小华第1种材料有1个，第2种材料有1个，第3种材料有1个，另外还有1

个万能材料。组装一个玩具需要第1种材料10个，需要第2种材料10个，需要第3种材料

10个。所有小华目前的材料只能组装0个玩具。

【样例3解释】

输入中小华第1种材料有13个，第2种材料有7个，第3种材料有20个，另外还有1

个万能材料。组装一个玩具需要第1种材料3个，需要第2种材料2个，需要第3种材料5

个。小华将万能材料作为1个第2种材料，可以组装4个玩具。

【样例4解释】

输入中小华第1种材料有3个，第2种材料也有3个，另外还有2个万能材料。组装一

个玩具需要第1种材料2个，需要第2种材料2个。小华将1个万能材料作为1个第1种材

料，将另外1个万能材料作为1个第2种材料，则可以组装2个玩具。

【数据范围约定】

50%的测试点输入数据保证$1≤n≤1000, 1≤m≤10^4，1≤Xi, Yi≤10^4$。

100%的测试点输入数据保证$1≤n≤100000, 1≤m≤10^9，1≤Xi, Yi≤10^9$。