Description

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

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

Format

Input

输入共3行。

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

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

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

Output

输出共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

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

100%的测试点输入数据保证1 ≤ n ≤ 10000,1 ≤m≤ 10⁹,1 ≤ Xi ,Yi ≤ 10⁹.