Problem Description

Having realized his charm, Katsu-san decided to open a shop selling cutlet sandwiches.

The shop will be open for $ N $ days, and on the $ i $th day, $ A_i $ pieces of bread and $ B_i $ pieces of cutlet will be delivered. A cutlet sandwich can be made using $ 2 $ pieces of bread and $ 1 $ piece of cutlet.

Determine the maximum number of cutlet sandwiches Katsu-san can make over the $ N $ days. Note that leftover ingredients must be discarded at the end of each day and cannot be used on another day.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_N $ $ B_N $

Output Format

Output the maximum number of cutlet sandwiches Katsu-san can make over the $ N $ days.

Sample Input and Output

Sample Input #1

3
10 5
100 1
1 100

Sample Output #1

6

Sample Input #2

7
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Sample Output #2

3500000000

Notes/Hints

Constraints

The input satisfies the following conditions:

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^9$
• All input values are integers

Sample Explanation 1

• On the 1st day, exactly $ 5 $ cutlet sandwiches can be made.
• On the 2nd day, only $ 1 $ cutlet sandwich can be made using $ 2 $ pieces of bread and $ 1 $ piece of cutlet, leaving a lot of bread.
• On the 3rd day, no cutlet sandwiches can be made because there is only $ 1 $ piece of bread, leaving a lot of cutlets.
• In total, $ 5 + 1 + 0 = 6 $ cutlet sandwiches can be made.

见题面 Input 部分

见题面 Output 部分