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_{i} and width of lawn g_{i}. [Image] 

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_{i} (0 ≤ x_{i} ≤ g_{i}). After it new road width of the i-th part will be equal to s'_{i} = s_{i} + x_{i} and new lawn width will be equal to g'_{i} = g_{i} - x_{i}.

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 < n) the inequation |s'_{i} + 1 - s'_{i}| ≤ 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.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2·10^5) — number of parts of the street.

Each of the following n lines contains two integers s_{i}, g_{i} (1 ≤ s_{i} ≤ 10^6, 0 ≤ g_{i} ≤ 10^6) — current width of road and width of the lawn on the i-th part of the street.


-----Output-----

In the first line print the total width of lawns which will be removed.

In the second line print n integers s'_1, s'_2, ..., s'_{n} (s_{i} ≤ s'_{i} ≤ s_{i} + g_{i}) — new widths of the road starting from the first part and to the last.

If there is no solution, print the only integer -1 in the first line.


-----Examples-----
Input
3
4 5
4 5
4 10

Output
16
9 9 10 

Input
4
1 100
100 1
1 100
100 1

Output
202
101 101 101 101 

Input
3
1 1
100 100
1 1

Output
-1

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Implementation

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = int(input())
s = [0] * n
g = [0] * n
for i in range(n):
	(a, b) = list(map(int, input().split()))
	s[i] = a
	g[i] = a + b
for i in range(1, n):
	g[i] = min(g[i], g[i - 1] + 1)
for i in range(n - 2, -1, -1):
	g[i] = min(g[i], g[i + 1] + 1)
ans = 0
for i in range(n):
	if s[i] <= g[i]:
		ans += g[i] - s[i]
	else:
		print(-1)
		break
else:
	print(ans)
	print(*g)


from random import choice, randint
from string import ascii_uppercase, ascii_letters, digits, ascii_lowercase
from sys import stdin, stdout
from random import choice
from functools import reduce
import time
from math import *
from itertools import combinations
from decimal import *
n = int(stdin.readline())
(maxs, ans) = ([], [])
arr = [0] * n
arr1 = [0] * n
cmin = -10 ** 12
tmp = cmax = 10 ** 12
for i in range(n):
	(s, g) = map(int, stdin.readline().split())
	arr[i] = s
	arr1[i] = g
	cmax = min(s + g, cmax + 1)
	cmin = max(cmin - 1, s)
	if cmax < cmin:
		stdout.write('-1')
		exit()
	maxs.append(cmax)
for i in range(n - 1, -1, -1):
	tmp = min(tmp + 1, maxs[i])
	ans.append(tmp)
stdout.write(str(sum(ans) - sum(arr)) + '\n')
for i in ans[::-1]:
	stdout.write(str(i) + ' ')


n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
	a[i][1] += a[i][0]
for i in range(1, n):
	if a[i][1] > a[i - 1][1] + 1:
		a[i][1] = a[i - 1][1] + 1
		if a[i][1] < a[i][0]:
			exit(print(-1))
s = a[-1][1] - a[-1][0]
for i in range(n - 2, -1, -1):
	if a[i][1] > a[i + 1][1] + 1:
		a[i][1] = a[i + 1][1] + 1
		if a[i][1] < a[i][0]:
			exit(print(-1))
	s += a[i][1] - a[i][0]
print(s)
for i in a:
	print(i[1], end=' ')


n = int(input())
ss = [0] * (n + 1)
gg = [0] * (n + 1)
maxs = [0] * n
curMin = -10 ** 10
curMax = -curMin
for i in range(n):
	(s, g) = map(int, input().split(' '))
	ss[i] = s
	gg[i] = g
	curMin = max(curMin - 1, s)
	curMax = min(curMax + 1, s + g)
	if curMin > curMax:
		print(-1)
		exit(0)
	maxs[i] = curMax
res = [0] * n
cur = 10 ** 10
for i in range(n - 1, -1, -1):
	res[i] = cur = min(cur + 1, maxs[i])
print(sum(res) - sum(ss))
print(*res)


t = []
l = []
r = []
for _ in range(int(input())):
	(s, g) = map(int, input().split())
	t.append(s)
	l.append(s)
	r.append(g + s)
for i in range(1, len(l)):
	if l[i] < l[i - 1]:
		l[i] = l[i - 1] - 1
	if r[i] > r[i - 1]:
		r[i] = r[i - 1] + 1
for i in range(len(l) - 2, -1, -1):
	if l[i] < l[i + 1]:
		l[i] = l[i + 1] - 1
	if r[i] > r[i + 1]:
		r[i] = r[i + 1] + 1
if [1 for (a, b) in zip(l, r) if a > b]:
	print(-1)
else:
	print(sum([b - a for (a, b) in zip(t, r)]))
	print(' '.join(map(str, r)))


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
s = []
g = []
forwardBound = []
backwardBound = []
for _ in range(n):
	(sCur, gCur) = map(int, input().split())
	s.append(sCur)
	g.append(gCur)
forwardBound.append(s[0] + g[0])
for i in range(1, n):
	if forwardBound[-1] < s[i] + g[i]:
		forwardBound.append(forwardBound[-1] + 1)
	else:
		forwardBound.append(s[i] + g[i])
backwardBound.append(s[n - 1] + g[n - 1])
for i in range(1, n):
	if backwardBound[-1] < s[n - i - 1] + g[n - i - 1]:
		backwardBound.append(backwardBound[-1] + 1)
	else:
		backwardBound.append(s[n - i - 1] + g[n - i - 1])
validity = True
ans1 = 0
ans = []
for i in range(n):
	if s[i] > min(forwardBound[i], backwardBound[n - i - 1]):
		validity = False
		break
	else:
		ans.append(str(min(forwardBound[i], backwardBound[n - i - 1])))
		ans1 += min(forwardBound[i], backwardBound[n - i - 1]) - s[i]
if validity:
	print(ans1)
	print(' '.join(ans))
else:
	print(-1)


import heapq
from heapq import heappush as push_
from heapq import heappop as pop_
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
Q = []
d = [s + g for (s, g) in p]
for (i, [s, g]) in enumerate(p):
	push_(Q, (s + g, i))
flg = True
while len(Q) > 0:
	(S, ind) = pop_(Q)
	if S > d[ind]:
		continue
	if ind > 0 and d[ind - 1] > S + 1:
		if S + 1 < p[ind - 1][0]:
			flg = False
			break
		d[ind - 1] = S + 1
		push_(Q, (d[ind - 1], ind - 1))
	if ind < n - 1 and d[ind + 1] > S + 1:
		if S + 1 < p[ind + 1][0]:
			flg = False
			break
		d[ind + 1] = S + 1
		push_(Q, (d[ind + 1], ind + 1))
if flg == False:
	print(-1)
else:
	print(sum([d[i] - p[i][0] for i in range(n)]))
	print(' '.join([str(x) for x in d]))