Maximum Throughput

Scaling up service i once costs cost[i], and after t scale-ups its throughput is tp[i]*(1+t). The throughput of the serial pipeline is the minimum over all services; find the maximum throughput with a total cost not exceeding the budget.

输入格式

The first line contains n budget, the second line contains n values of tp, and the third line contains n values of cost. Original OCR001/002 gives no numeric bounds; this site uses 1≤n≤100000, 0≤tp≤10^9, 1≤cost≤10^9, and 0≤budget≤10^9. Positive costs explicitly rule out unlimited free scale-ups, and a throughput of 0 can never be increased.

输出格式

Output one integer answer.

样例 1

输入：

3 32
4 2 7
3 5 6

输出：

10

样例 2

输入：

1 0
2
3

输出：

2

样例 3

输入：

2 10
0 8
1 2

输出：

0

样例说明

The outputs of the three public examples are, in order: 10; 2; 0. They have been checked by independent enumeration or direct simulation.