Alloy Production

Each unit of alloy needs composition[i] units of metal i; you already have stock[i] and can buy more at a unit price of cost[i], with a budget of budget. Find the maximum number of units you can produce.

This site uses a standard input/output protocol.

输入格式

The first line contains n budget; the next three lines are composition, stock, and cost respectively. Constraints added by this site: 1≤n≤100000, 0≤budget≤10^9, 1≤composition[i],cost[i]≤10^9, 0≤stock[i]≤10^9.

输出格式

Output the maximum number of alloy units.

样例 1

输入：

2 3
1 2
0 1
1 1

输出：

1

样例 2

输入：

1 0
2
10
4

输出：

5

样例 3

输入：

2 5
1 1
0 0
2 3

输出：

1