Cửa hàng kem lạnh

Một ngày hè nóng nực, hai người bạn nhỏ Hưng và Minh ghé vào một cửa hàng bán \(n\) loại kem khác nhau, với loại kem thứ \(i\) có giá \(c_i\).

Họ muốn mua \(m\) cây kem. Minh đề xuất một cách chia tiền như sau:

Nếu cây kem có giá nhỏ hơn \(k\), Hưng sẽ trả toàn bộ số tiền.

Ngược lại, Hưng chỉ trả \(k\) đồng, phần còn lại (tức là \(c_i - k\)) sẽ do Minh trả.

Gọi \(l\) là tổng tiền Hưng phải trả, và \(f\) là tổng tiền Minh phải trả. Hưng cảm thấy cách chia tiền này không công bằng nên muốn chọn ra \(m\) cây kem sao cho biểu thức \(l - f\) nhỏ nhất có thể.

Bạn được yêu cầu tính giá trị nhỏ nhất của \(l - f\) cho mỗi trong \(q\) truy vấn, mỗi truy vấn cung cấp một giá trị \(k\) và \(m\).

Input

\begin itemize

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)) --- số lượng cây kem và số truy vấn.

• Dòng thứ hai chứa \(n\) số nguyên \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le 10^9\)) --- giá của từng loại kem.

• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(k_i\) và \(m_i\) (\(1 \le k_i \le 10^9\), \(1 \le m_i \le n\)) --- truy vấn thứ \(i\).

Output

Gồm \(q\) dòng, mỗi dòng ghi giá trị nhỏ nhất của biểu thức \(l - f\) tương ứng với truy vấn thứ \(i\).

Example

5 2
1 9 22 10 19
18 4
5 2

34
-21

7 4
1 5 4 3 7 11 9
5 4
5 7
7 3
4 5

4
16
7
1

Scoring

• Subtask 1 (30 điểm): \(n, q \le 1000\), \(c_i, k_i \le 10^6\).
• Subtask 2 (30 điểm): \(k_1 = k_2 = \dots = k_n\).
• Subtask 3 (40 điểm): Không có ràng buộc bổ sung.