题目描述

小华打算用 n 种(编号为1到 n )材料组装玩具。

其中第 i 种材料的数量为 $X_i$ 个。组装一个玩具需要第 i 种材料 $Y_i$ 个。

小华另外有 m 个万能材料，每个万能材料可以作为 n 种材料中的任意一个材料使用。

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

输入格式
共3行：

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

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

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

数据范围

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

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

输出格式

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

样例

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

样例解释

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

2. 样例 2 ：输入中小华第 1 种材料有 1 个,第 2 种材料有 1 个,第 3 种材料有 1 个,另外还有 1 个万能材料。组装一个玩具需要第 1 种材料 10 个,需要第 2 种材料 10 个,需要第 3 种材料 10 个。所有小华目前的材料只能组装 0 个玩具。

3. 样例 3 ：输入中小华第 1 种材料有 13 个，第 2 种材料有 7 个，第 3 种材料有 20 个，另外还有 1 个万能材料。组装一个玩具需要第1种材料3个，需要第2种材料2个，需要第3种材料5个。小华将万能材料作为 1 个第 2 种材料，可以组装 4 个玩具。

4. 样例4：输入中小华第 1 种材料有 3 个，第 2 种材料也有 3 个，另外还有 2 个万能材料。组装一个玩具需要第 1 种材料 2 个，需要第 2 种材料 2 个。小华将 1 个万能材料作为 1 个第1种材料，将另外 1 个万能材料作为 1 个第 2 种材料，则可以组装 2 个玩具。