Hay Weight

Farmer Bajtazar has bought a field of area $n$ ares, where he plans to sow grass. The cut and dried grass will serve as feed for the animals raised on Bajtazar's farm.

A mixture of $n$ grass species will be sown in the field. Each species will occupy 1 are of land in total. For the $i$-th species, a blade of grass grows by $a_i$ centimeters per day, regardless of weather conditions and soil fertility. It is also known that cutting one centimeter of grass over an area of one are yields exactly 1 kilogram of hay.

Bajtazar has a mower that can be set to cut grass to any height $b$. With this setting, every blade of grass taller than $b$ centimeters is cut to exactly $b$ centimeters.

Bajtockie law requires that after each mowing, the amount of hay obtained from the cut grass be documented. Bajtazar faces a choice: he must either buy a scale or write a program that, based on the mowing dates and mower settings, estimates the weight of hay obtained after each mowing. The second option seemed more convenient and cheaper to him.

We assume that the grass is sown on day 0 at midnight and is always mowed at midnight. We also assume that the time needed to mow the field to any height $b$ is negligibly small.

The first line of input contains two integers $n$ and $m$ ($1 \le n, m \le 500\,000$), denoting Bajtazar's field area in ares (and also the number of sown grass species) and the number of mowings. The second line contains a sequence of $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$) denoting the growth rates of the successive grass species.

The next $m$ lines contain descriptions of the mowings performed by Bajtazar. The $i$-th mowing is described by the two integers $d_i$ and $b_i$ ($1 \le d_i \le 10^{12}$, $0 \le b_i \le 10^{12}$) on the $i$-th of these lines, meaning that on day $d_i$ Bajtazar cut the grass to a length of $b_i$ centimeters. You may assume that the mowing descriptions are given in chronological order, i.e., $d_1 < d_2 < \ldots < d_m$.

Furthermore, you may assume that Bajtazar never lets the grass in any part of the field reach a height exceeding $10^{12}$ centimeters.

Output exactly $m$ lines. The $i$-th line should contain the total weight of hay (in kilograms) obtained after the $i$-th mowing.

The table below shows the blade heights of grass species 1, 2, 3, 4 before and after each mowing.