Pipeline Throughput Maximization Under Budget

Scaling service i up x times costs x×cost[i] and changes its throughput to base[i]×(1+x), where x is a non-negative integer. The throughput of a serial pipeline is the minimum over all services. Find the maximum throughput within the total budget.

This site has made the standard input and output explicit.

输入格式

The first line contains n budget, the second line contains base, and the third line contains cost. On this site 1≤n≤100000, 1≤base[i],cost[i]≤10⁹, 0≤budget≤10⁹.

输出格式

Output one integer, the answer.

样例 1

输入：

3 0
5 2 4
3 10 2

输出：

2

样例 2

输入：

3 20
5 2 4
3 10 2

输出：

4

样例 3

输入：

1 5
3
2

输出：

9

样例说明

Example 1: with no budget, the bottleneck is 2. Example 2: throughput 4 needs a budget of 10; throughput 5 needs 22, which exceeds 20, so the maximum is 4, and the budget does not have to be spent completely. Example 3: at most two scale-ups, giving throughput 3×3=9.