Mở rộng lòng đường

Một con đường được chia thành $n$ đoạn bằng nhau, đánh số từ trái sang phải. Đoạn thứ $i$ có bề rộng phần lòng đường là $s_i$ và bề rộng phần bãi cỏ là $g_i$.

Với mỗi đoạn $i$, ta có thể phá bỏ một phần bãi cỏ với độ rộng nguyên $x_i$ ($0\le x_i\le g_i$). Sau đó, bề rộng lòng đường mới của đoạn $i$ trở thành $s_i^{\prime }=s_i+x_i$ và bề rộng bãi cỏ còn lại là $g_i-x_i$.

Ta muốn phá bỏ càng nhiều bãi cỏ càng tốt, đồng thời tránh việc lòng đường thay đổi bề rộng quá đột ngột giữa các đoạn liền kề. Cụ thể, với mọi $i$ ($1\le i<n$) phải thỏa mãn $|s_{i+1}^{\prime }-s_i^{\prime }|\le 1$. Lưu ý điều kiện này có thể chưa đúng với cấu hình ban đầu.

Hãy tìm tổng độ rộng bãi cỏ lớn nhất có thể phá bỏ (tức là tối đa ${\sum }_{i=1}^n{x}_i$), và đưa ra một cấu hình bề rộng lòng đường mới đạt được tổng đó. Nếu không tồn tại cấu hình hợp lệ nào, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số đoạn của con đường.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $s_i$ và $g_i$ là bề rộng lòng đường và bề rộng bãi cỏ hiện tại của đoạn $i$.

Dữ liệu ra

• Nếu không có cấu hình hợp lệ, in ra một số $-1$.
• Ngược lại, dòng đầu in tổng độ rộng bãi cỏ lớn nhất bị phá bỏ. Dòng thứ hai in $n$ số nguyên $s_1^{\prime },s_2^{\prime },\dots ,s_n^{\prime }$ ($s_i\le s_i^{\prime }\le s_i+g_i$) là bề rộng lòng đường mới của các đoạn.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le s_i\le {10}^6$
• $0\le g_i\le {10}^6$

Ví dụ