Mayor of city S just hates trees and lawns. They take so much space and there could be a road on the place they occupy!

The Mayor thinks that one of the main city streets could be considerably widened on account of lawn nobody needs anyway. Moreover, that might help reduce the car jams which happen from time to time on the street.

The street is split into *n* equal length parts from left to right, the *i*-th part is characterized by two integers: width of road *s*<sub class="lower-index">*i*</sub> and width of lawn *g*<sub class="lower-index">*i*</sub>.

For each of *n* parts the Mayor should decide the size of lawn to demolish. For the *i*-th part he can reduce lawn width by integer *x*<sub class="lower-index">*i*</sub> (0 ≤ *x*<sub class="lower-index">*i*</sub> ≤ *g*<sub class="lower-index">*i*</sub>). After it new road width of the *i*-th part will be equal to *s*'<sub class="lower-index">*i*</sub> = *s*<sub class="lower-index">*i*</sub> + *x*<sub class="lower-index">*i*</sub> and new lawn width will be equal to *g*'<sub class="lower-index">*i*</sub> = *g*<sub class="lower-index">*i*</sub> - *x*<sub class="lower-index">*i*</sub>.

On the one hand, the Mayor wants to demolish as much lawn as possible (and replace it with road). On the other hand, he does not want to create a rapid widening or narrowing of the road, which would lead to car accidents. To avoid that, the Mayor decided that width of the road for consecutive parts should differ by at most 1, i.e. for each *i* (1 ≤ *i* &lt; *n*) the inequation |*s*'<sub class="lower-index">*i* + 1</sub> - *s*'<sub class="lower-index">*i*</sub>| ≤ 1 should hold. Initially this condition might not be true.

You need to find the the total width of lawns the Mayor will destroy according to his plan.
The first line contains integer *n* (1 ≤ *n* ≤ 2·10<sup class="upper-index">5</sup>) — number of parts of the street.

Each of the following *n* lines contains two integers *s*<sub class="lower-index">*i*</sub>, *g*<sub class="lower-index">*i*</sub> (1 ≤ *s*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>, 0 ≤ *g*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>) — current width of road and width of the lawn on the *i*-th part of the street.
none
3
4 5
4 5
4 10
16
9 9 10 
4
1 100
100 1
1 100
100 1
202
101 101 101 101 
3
1 1
100 100
1 1
-1
10
21005 10850
27020 13372
28183 3724
22874 13564
27446 11493
22522 10012
24819 11529
24166 11084
24539 9211
24152 9235
71869
31855 31856 31857 31858 31859 31860 31861 31862 31863 31864 
1
1 0
0
1 
1
1 1000000
1000000
1000001 
1
1000000 1000000
1000000
2000000 
1
1 0
0
1 
1
1 0
0
1 
1
1 1
1
2 
2
2 2
1 1
2
3 2 
2
2 0
1 0
0
2 1 
2
2 1
2 2
3
3 4 
3
1 3
2 1
3 0
4
4 3 3 
3
1 3
1 3
2 1
7
4 4 3 
3
3 3
2 0
1 2
2
3 2 3 
4
1 3
2 3
3 1
1 0
-1
4
1 2
4 2
4 2
4 2
5
3 4 5 6 
4
1 3
1 4
2 0
4 1
-1
5
3 5
4 5
1 0
2 3
1 1
-1
5
2 0
3 0
3 0
3 5
2 4
4
2 3 3 4 5 
5
1 0
4 2
1 5
1 5
1 4
-1
6
1 1
3 4
3 5
2 5
6 3
2 3
8
2 3 4 5 6 5 
6
5 3
4 4
5 5
1 2
6 3
6 4
-1
6
1 5
6 2
2 1
1 2
3 6
1 1
-1
7
3 0
1 5
7 7
6 5
1 6
1 6
7 2
-1
7
7 5
1 2
3 0
3 1
4 5
2 6
6 3
-1
7
3 1
5 0
4 1
7 5
1 3
7 6
1 4
-1
8
4 2
8 8
4 1
7 7
1 3
1 1
3 1
5 2
-1
8
4 2
1 1
1 5
6 8
5 7
8 8
6 2
8 8
-1
8
4 6
3 8
7 4
5 0
8 7
8 8
8 8
3 5
-1
9
5 3
1 8
2 2
2 7
5 6
1 5
2 0
1 6
3 9
-1
9
4 7
2 0
7 3
9 5
8 8
6 5
6 8
5 3
8 7
-1
9
3 8
7 7
8 8
7 3
9 6
6 8
4 1
7 0
7 0
-1
10
1 8
5 8
7 9
9 4
3 4
5 3
1 3
2 4
6 6
5 7
-1
10
9 9
10 4
1 9
4 8
9 6
9 6
1 7
1 7
10 0
4 1
-1
10
3 10
8 5
4 1
8 4
8 8
9 1
6 0
10 6
7 7
6 0
-1
1
1000000 0
0
1000000 
2
1000000 0
999999 0
0
1000000 999999 
2
1000000 0
999998 1
1
1000000 999999 
2
1000000 1000000
1000000 1000000
2000000
2000000 2000000 
def argmin(start, end):
    m = float("inf")
    index = -1
    for i in range(start, end + 1):
        if sum(pairs[i]) < m:
            m = sum(pairs[i])
            index = i
    return index


def f(start, end):
    global s
    if start == end:
        return
    index = argmin(start, end)
    pairs[index][0] = sum(pairs[index])
    s += pairs[index][1]
    pairs[index][1] = 0
    if index > 0:
        if sum(pairs[index - 1]) > pairs[index][0]:
            pairs[index - 1][0] += 1 + pairs[index][0] - pairs[index - 1][0]
            pairs[index - 1][1] -= (1 + pairs[index][0] - pairs[index - 1][0])
            s += 1 + pairs[index][0] - pairs[index - 1][0]
        else:
            pairs[index - 1][0] += pairs[index][0] - pairs[index - 1][0]
            pairs[index - 1][1] -= (pairs[index][0] - pairs[index - 1][0])
            s += pairs[index][0] - pairs[index - 1][0]
        f(start, index - 1)

    if index < n - 1:
        if sum(pairs[index + 1]) > pairs[index][0]:
            pairs[index + 1][0] += (1 + pairs[index][0] - pairs[index + 1][0])
            pairs[index + 1][1] -= (1 + pairs[index][0] - pairs[index + 1][0])
            s += 1 + pairs[index][0] - pairs[index + 1][0]
        else:
            pairs[index + 1][0] += (pairs[index][0] - pairs[index + 1][0])
            pairs[index + 1][1] -= (pairs[index][0] - pairs[index + 1][0])
            s += pairs[index][0] - pairs[index + 1][0]
        f(index + 1, end)


n = int(input())
pairs = [[int(a) for a in input().split()] for _ in range(n)]
s = 0
f(0, n - 1)
print(s)
print([x[0] for x in pairs])
