### PROBLEM LINK:

**Author:** Dmytro Berezin

**Tester:** Sergey Kulik

**Editorialist:** Lalit Kundu

### DIFFICULTY:

EASY

### PREREQUISITES:

AD-HOC

### PROBLEM:

There is a N * M matrix, where A*[j] is j for all i,j. There are P queries of form (i,j), where we do A*[j]++.

For each row i,

if there exists a j, such that A*[j] > A*[j+1], print -1.

else print sum[i=M to 2]{A*[j]-A*[j-1]}.

1 ≤ N,M,P ≤ 10^{5}

### QUICK EXPLANATION:

For each i, we also keep note of values (i,j-1) and (i,j+1), if (i,j) is given in input. Traversing over the queries, we can see which values change and print answer accordingly.

### EXPLANATION:

We have to process for each i independently. Let’s say for an i, we have NN queries of form (j,k) which means: increase A*[j] by k. For such a query we also store (j-1,0) and (j+1,0), because these two indexes are also effected.

If there were no changes, our answer will be m-1. Now, we traverse over all queries in increasing order of j and look at index j+1, if the value at j+1 is less than value at j, we know that answer is -1 for this row. Else, we add the (A*[j+1]-A*[j]) to the answer and subtract -1 from the answer. We can use map to perform this process efficiently. See (setter/tester/editorialist)'s solution for implementation details.