Uniform Daily Rounds in Dance Game

Fusu is an avid dancer in the popular dance game. For the next n days, she wants to play the game and complete the same number of rounds each day. Each round costs exactly 1 game coin. However, the twist is that the exchange rate for game coins varies from day to day. Specifically, on the i-th day, 1 Yuan can purchase a_i game coins.

Moreover, thanks to her side‐jobs, she will earn b_i Yuan on the i-th day. The daily procedure is as follows:

• At the start of the day she receives her income of b_i Yuan.
• She may then use any part of the money she owns to purchase game coins at that day’s rate. (Money that is not used can be carried over to future days.)
• She then spends exactly 1 game coin per round to play the game. Coins that are not used can also be saved for future days.

Fusu wants to know the maximum number of rounds t she can play each day over the next n days if she optimally chooses when to purchase coins. Note that she is allowed to postpone purchasing coins on a day if she anticipates a better exchange rate in the future – as long as she has enough coins to play on that day. On any day, if her current coin reserve is insufficient to cover the t rounds, she may purchase just enough coins with the money she currently has. Furthermore, at the end of each day, after playing the rounds, if the current day’s exchange rate is strictly better than all future days' rates, it is optimal to convert all remaining cash into coins.

Your task is to determine the maximum integer t (number of rounds per day) that Fusu can achieve over the n days.

Note on optimal strategy: Since money can be carried over unspent, Fusu should wait to exchange her cash until she is forced to buy coins for that day or until the current day’s exchange rate is higher than any future day’s rate.

All formulas are rendered in LaTeX format.

The key details in formula form:

• Each round costs \(1\) coin.
• On day \(i\): 1 Yuan buys \(a_i\) coins and she earns \(b_i\) Yuan.
• If on day \(i\) her coin reserve is less than \(t\), she must buy at least \(t - ({\rm coins\,in\,reserve})\) coins by spending \(\frac{t - ({\rm coins\,in\,reserve})}{a_i}\) Yuan.
• If \(a_i > \max\{a_{j} : j > i\}\), then converting all remaining cash to coins is optimal.

inputFormat

The first line contains a positive integer \(n\) (the number of days).

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the number of game coins one can get for 1 Yuan on each day.

The third line contains \(n\) space-separated integers \(b_1, b_2, \dots, b_n\) where \(b_i\) is the amount of Yuan Fusu earns on day \(i\).

outputFormat

Output a single integer, the maximum number \(t\) of rounds Fusu can play each day under an optimal coin purchasing strategy.

sample

2
1 2
1 1

1