Barossa Valley, South Australia, is world-famous for its rich, bold red wines. Your university friends want to "Surf the Barossa" with a full-day wine your, and you're joining.

Each winery on the tour offers a wine tasting package, consisting of:

• ~R_i~ glasses of red wine, and
• ~W_i~ glasses of white wine.

You must choose a contiguous block of wineries to visit and drink from, in order. If you visit a winery, you consume all glasses in its package simultaneously. Your goal is to maximise the total number of glasses consumed to appear properly cultured.

But... you actually hate red wine. No offense to the craft, but it's not for you. So, at no point in your tastings should the total number of red wine glasses consumed exceed the total number of white wine glasses. Otherwise, you will throw up, and your friends won't think you're cultured.

What is the maximum number of glasses of wine you can drink without throwing up?

Input

The first line contains a single integer, ~n~ (~1 \leq n \leq 10^5~), the number of wineries on the tour.

The next ~n~ lines contain ~R_i~ and ~W_i~ (~1 \leq R_i, W_i \leq 10^8~), indicating that the ~i~th winery has ~R_i~ red wines and ~W_i~ white wines in its tasting package.

Output

Output the maximum number of wines you can drink from any contiguous block of wine tastings on the tour.

Clarifications

A "contiguous block" refers to a set of adjacent wine tastings with no breaks in-between.

Example

Input 1

5
5 3
3 4
6 5
2 5
8 2

Output 1

25

Start at the second winery, and keep drinking up until (and including) the fourth winery. Your wine counts are as follows:

• After the second winery, you've drunk ~3~ reds and ~4~ whites. ~R_{total} \leq W_{total}~, so you don't throw up.
• After the third winery, you've drunk ~9~ reds and ~9~ whites. ~R_{total} \leq W_{total}~, so you don't throw up.
• After the fourth winery, you've drunk ~11~ reds and ~14~ whites. ~R_{total} \leq W_{total}~, so you don't throw up.

You drink ~25~ glasses of wine from this contiguous set of wineries. It can be shown that this is the maximum number of wines you can drink without throwing up.

Input 2

4
1 2
5 1
1 2
5 1

Output 2

3

It's impossible to drink at more than one of the wineries without throwing up.