19492번 - Hay 다국어

Byteasar, a farmer, bought a field of area equal to $n$ ares, where he intends to sow grass seeds. Mown and dried hay will be used as a fodder for livestock kept on Byteasar's farm.

A mix of $n$ grass species will be sown in the field -- each species will take up a total of $1$ ares. For the $i$-th species it is known that its grass blades grow by $a_i$ centimetres each day, regardless of weather conditions or soil fertility. It is also known that as a result of mowing one are of any grass type by one centimetre, exactly $1$ kilogram of hay is obtained.

Byteasar has a mower that can be set in such a way that it cuts grass to any height $b$. With this setting each blade of grass higher than $b$ centimetres will be trimmed down to the height of exactly $b$ centimetres.

Byteotian law requires that after each grass mowing the amount of hay obtained is to be documented. Byteasar faced a choice: he must either buy a weighing machine, or write a program that based on the dates of mowing and mowers settings, could estimate the weight of the hay obtained after each mowing. The second of these options seemed more convenient and cheaper to him.

We assume that the grass will be sown on day $0$ at midnight and always be mown at midnight. We also assume that the time it takes to mow the grass in the field to any height $b$ is negligible.

The first line of input contains two integers $n$ and $m$ ($1\leq n,m\leq 500\,000$), denoting Byteasar's field area in ares (and at the same time the number of grass species sown) and the number of times the grass has been mown. The second line contains a sequence of $n$ integers $a_1, a_2, \ldots, a_n$ ($1\leq a_i\leq 10^6$) indicating the rate of growth of successive species of grass.

The next $m$ lines contain the details of how Byteasar mowed the grass: the $i$-th mowing is described by two integers $d_i$ and $b_i$ ($1\leq d_i \leq 10^{12}$, $0\leq b_i \leq 10^{12}$) contained in the $i$-th of these lines and indicating that on day $d_i$ Byteasar trimmed the grass to the length of $b_i$ centimetres. You can assume that this data is listed in chronological order, i.e., $d_1 < d_2 < \ldots < d_m$.

Furthermore, you can also assume that Byteasar would never allow a situation when the grass has height exceeding $10^{12}$ centimetres at any place in the field.

The output should contain exactly $m$ lines. The $i$-th of these lines should include a total weight of hay (in kilograms) obtained after the $i$-th grass mowing.