Simulated Grass Mowing

Farmer Byteasar owns a field of \(n\) acres. On each acre \(i\) he planted a unique type of grass that grows at a rate of \(a_i\) centimeters per day. He will perform \(m\) mowing events. The \(j\)th mowing event takes place on day \(d_j\). During this event, for every acre, if the current grass height is at least \(b_j\) centimeters, then the portion above \(b_j\) is cut off, leaving the grass at exactly \(b_j\) centimeters. The amount of grass cut from that acre is the excess height, i.e.,
\(\max(0, h - b_j)\) where \(h\) is the current height before the cut.

Initially, at day 0, the grass on every acre has height 0. Between events the grass continues growing at its specified rate. In other words, if the previous mowed height on acre \(i\) is \(h_i\), then by day \(d_j\) its height becomes \(h_i + a_i \times (d_j - d_{\text{prev}})\), where \(d_{\text{prev}}\) is the day of the previous mowing event (or 0 for the first event). Then, if the updated height is \(\ge b_j\), the amount of grass cut from this acre is \(h_i + a_i(d_j - d_{\text{prev}}) - b_j\) and its height resets to \(b_j\); otherwise, nothing is cut.

Your task is to compute, for each mowing event, the total height of the grass that is cut (i.e. the sum over all acres of the height removed during that event).

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, representing the number of acres and the number of mowing events respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(a_i\) is the growth rate (in centimeters per day) of the grass on the \(i\)th acre.

Each of the following \(m\) lines contains two integers \(d_j\) and \(b_j\) representing the day of the \(j\)th mowing event and the threshold height. It is guaranteed that the events are given in increasing order of \(d_j\).

outputFormat

Output \(m\) lines. The \(j\)th line should contain a single integer representing the total height of the grass that is cut during the \(j\)th mowing event.

sample

3 2
1 2 3
3 5
5 7

5
6