WeChat Step Count Challenge

Little C loves running and is obsessed with climbing the WeChat step count leaderboard. To achieve this, he formulated a plan on a k-dimensional grid. In this grid the position of a person is represented by integer coordinates \( (a_1, a_2, \ldots, a_k) \) and the grid has size restrictions: \(1 \le a_i \le w_i\) for \(1 \le i \le k\). Thus, the total number of positions in the grid is \(P = w_1 \times w_2 \times \cdots \times w_k\>.

Little C plans to start his step boosting routine from every position exactly once over the next \(P\) days. In each day, he follows a predetermined route consisting of \(n\) moves. The \(i\)-th move is described by two numbers \(c_i\) and \(d_i\) and means that if he is currently at \((a_1,a_2,\ldots,a_{c_i},\ldots,a_k)\), then he moves to \((a_1,a_2,\ldots,a_{c_i}+d_i,\ldots,a_k)\). Here \(1 \le c_i \le k\) and \(d_i \in \{-1, 1\}\). After performing the \(n\) moves, if he is still inside the grid, he repeats the same route (starting again at the first move) until eventually one of his moves takes him outside the grid, at which point his day ends.

Your task is to calculate the total number of steps taken over all \(P\) days. Note that if for any starting position Little C never leaves the grid (i.e. his plan continues forever), the answer is defined to be -1.

inputFormat

The first line contains two integers \(k\) and \(n\), representing the dimension of the grid and the number of moves in the route, respectively.

The second line contains \(k\) integers: \(w_1, w_2, \ldots, w_k\), where \(w_i\) denotes the size of the grid in the \(i\)-th dimension.

The next \(n\) lines each contain two integers \(c_i\) and \(d_i\), representing the dimension to move in and the direction (either -1 or 1) for the \(i\)-th move.

outputFormat

Output a single integer: the total number of steps taken over all \(P\) days. If the total number of steps is infinite, output -1.

sample

1 1
5
1 1

15