Road Widening

도시 S의 시장은 나무와 잔디밭을 몹시 싫어한다. 그것들은 너무 많은 공간을 차지하며, 그 자리에 도로가 놓일 수도 있기 때문이다!

The Mayor은 아무도 필요로 하지 않는 잔디밭을 이용하면 도시의 주요 도로 중 하나를 상당히 넓힐 수 있다고 생각한다. 게다가 그렇게 하면 이 도로에서 때때로 발생하는 교통 체증을 줄이는 데 도움이 될 수도 있다.

이 도로는 왼쪽에서 오른쪽으로 길이가 같은 n개의 구간으로 나뉘며, i-th 구간은 두 정수, 즉 도로의 너비 si와 잔디밭의 너비 gi로 나타낸다.

시장은 n개의 각 구간에 대해 철거할 잔디밭의 크기를 결정해야 한다. i-th 구간에서는 잔디밭의 너비를 정수 xi (0 ≤ xi ≤ gi)만큼 줄일 수 있다. 그러면 i-th 구간의 새로운 도로 너비는 s'i = si + xi가 되고, 새로운 잔디밭 너비는 g'i = gi - xi가 된다.

한편으로 시장은 가능한 한 많은 잔디밭을 철거하여 도로로 바꾸고 싶어 한다. 다른 한편으로는 교통사고를 일으킬 수 있는 도로의 급격한 확장이나 축소를 만들고 싶어 하지 않는다. 이를 피하기 위해 시장은 연속한 구간들의 도로 너비 차이가 최대 1이어야 한다고 결정했다. 즉, 각 i (1 ≤ i < n)에 대해 부등식 |s'i + 1 - s'i| ≤ 1이 성립해야 한다. 처음에는 이 조건이 성립하지 않을 수도 있다.

시장이 자신의 계획에 따라 철거할 잔디밭 너비의 총합을 구해야 한다.

첫 번째 줄에는 도로 구간의 수를 나타내는 정수 n (1 ≤ n ≤ 2·105)이 주어진다.

이어지는 n개의 각 줄에는 두 정수 si, gi (1 ≤ si ≤ 106, 0 ≤ gi ≤ 106)이 주어진다. 이는 도로의 i-th 구간에서 현재 도로의 너비와 잔디밭의 너비를 나타낸다.

첫 번째 줄에 제거할 잔디밭 너비의 총합을 출력한다.

두 번째 줄에 첫 구간부터 마지막 구간까지의 새로운 도로 너비를 나타내는 n개의 정수 s'1, s'2, ..., s'n (si ≤ s'i ≤ si + gi)을 출력한다.

해가 없다면 첫 번째 줄에 유일한 정수 -1을 출력한다.