Get Max Throughput

n services are connected in series, and the total throughput is the minimum throughput among the services. Each scale-up of service i costs cost[i], and after x scale-ups its throughput is throughput[i]·(1+x). Find the maximum total throughput within the budget. The original formula (i+x) conflicts with the definition of initial throughput, and only (1+x) gives both 10 and 9 for the two original examples, so the typo is restored based on this evidence.

输入格式

The first line contains n budget, the second line contains throughput, and the third line contains cost. The original gave no numeric bounds; this site uses 1≤n≤100000, 1≤throughput and per-scale-up cost≤10^9, and 0≤budget≤10^12. The answer and intermediate products can exceed 64 bits, so use exact integers or 128-bit integers.

输出格式

Output a single integer, the answer.

样例 1

输入：

3 32
4 2 7
3 5 6

输出：

10

样例 2

输入：

4 25
7 3 4 6
2 5 4 3

输出：

9

样例 3

输入：

1 0
3
2

输出：

3

样例说明

The outputs of the three public examples are, in order: 10; 9; 3. These answers were verified by independent enumeration or direct simulation.