Hay Delivery Waste Minimization

Farmer John owns N barns located at integer positions on a number line at coordinates \(x_1, x_2, \ldots, x_N\) (with \(0 \le x_i \le 10^6\)). He needs to deliver one hay load to each barn. The hay loads are initially located at some integer point \(y\) (with \(0 \le y \le 10^6\)). However, the transportation system wastes hay along the way. Specifically, when a hay load is moved from \(y\) to a barn at \(x\):

• If \(y > x\) (i.e. the hay load moves left), it wastes \(a \cdot (y-x)\) hay piles.
• If \(x > y\) (i.e. the hay load moves right), it wastes \(b \cdot (x-y)\) hay piles.

You are given Q independent queries. In each query the values of a and b are provided, and Farmer John may choose the best integer location \(y\) in order to minimize the total wasted hay. Compute, for each query, the minimum total number of wasted hay piles when \(y\) is chosen optimally.

The cost of delivering a load to barn at \(x\) when using delivery point \(y\) can be written in LaTeX as:

[ \text{cost}(x, y)= \begin{cases} a\cdot (y-x) & \text{if } y > x, \ b\cdot (x-y) & \text{if } x > y, \ 0 & \text{if } x = y. \end{cases} ]

Observation: Since the cost function is convex in \(y\), an optimal location \(y\) will always be one of the barns' positions. For a chosen barn position \(x_i\) (assuming 0-indexing and the barns are sorted in non-decreasing order) the total wasted hay is:

[ \text{TotalCost}(i)= a\cdot\Bigl(i \cdot x_i - \sum_{j=0}^{i-1} x_j\Bigr) + b\cdot\Bigl(\Bigl(\sum_{j=i+1}^{N-1} x_j\Bigr) - (N-i-1), x_i\Bigr). ]

Your task is to process each query by choosing the barn (i.e. \(y=x_i\) for some \(i\)) that yields the least wasted hay.

inputFormat

The first line contains two integers \(N\) and \(Q\) (\(1 \le N \le 2\cdot 10^5\), \(1 \le Q \le 2\cdot 10^5\)).

The second line contains \(N\) integers \(x_1, x_2, \ldots, x_N\) where \(0 \le x_i \le 10^6\), representing the positions of the barns.

Then \(Q\) lines follow, each containing two integers \(a\) and \(b\) (\(1 \le a, b \le 10^6\)) representing one query.

outputFormat

For each query, output a single integer: the minimum total number of wasted hay piles.

sample

5 3
1 3 5 7 9
1 1
1 2
3 1

12
16
18