Bitaro's Monster Battle

Bitaro is on a quest to defeat a series of monsters. He starts with an initial strength x (to be determined). There are N monsters numbered from 1 to N. To defeat the i^th monster, his strength must be at least $$A_i$$. Once he defeats monster i, his strength increases by $$B_i$$.

Bitaro will fight the monsters following a cyclic strategy:

• He chooses an integer j (1 ≤ j ≤ N), and fights monsters in the order: j, j+1, …, N.
• If j ≥ 2, he then goes back and fights monsters 1, 2, …, j-1.

Under the condition that he must defeat all monsters by following this strategy, your task is to compute the minimum initial strength x Bitaro must have so that there exists a choice of j which allows him to defeat all monsters. Formally, if Bitaro chooses a starting index j and his strength sequence is updated as follows:

$$x_{0} = x, \quad x_{i} = x_{i-1} + B_{\sigma(i)} \quad (1 \le i \le N) $$

where (\sigma(1), \sigma(2), \dots, \sigma(N)) is the order of monsters encountered according to the chosen cyclic order, then for every fight we require:

$$x_{i-1} \ge A_{\sigma(i)} \quad \text{for } 1 \le i \le N. $$

You must determine the minimum possible x (with x ≥ 0) such that there exists a valid starting index j making the battle winnable.

inputFormat

The first line contains a single integer N representing the number of monsters. The next N lines each contain two integers A_i and B_i separated by a space, where:

• $$A_i$$ is the minimum strength required to defeat the i^th monster.
• $$B_i$$ is the amount of strength Bitaro gains after defeating the i^th monster.

You may assume that all input values are integers.

outputFormat

Output a single integer, the minimum initial strength x required for Bitaro to be able to defeat all monsters following some cyclic order strategy.

sample

1
10 3

10