Gian hàng của chương trình Xuân Tình Nguyện NBK có \(n\) món hàng, món hàng thứ \(i\) có giá tiền \(c_i\) đồng. Hương Giang và Bích Phương muốn chung tiền lại mua đúng \(m\) món hàng, vừa để ủng hộ chương trình, vừa muốn tặng cho các bạn trong khối K21. Hai bạn thống nhất quy tắc thanh toán đối với từng món hàng như sau:

• Nếu món hàng có giá tiền ít hơn \(k\) đồng, Hương Giang sẽ chịu trách nhiệm thanh toán toàn bộ.
• Ngược lại, Hương Giang sẽ thanh toán \(k\) đồng, còn Bích Phương sẽ thanh toán phần còn lại (tức \(c_i-k\) đồng).

Gọi \(l\) và \(f\) lần lượt là tổng số tiền mà Giang và Phương bỏ ra để mua hết \(m\) món hàng. Bạn hãy chọn \(m\) món hàng phù hợp từ danh sách \(n\) món hàng của Xuân Tình Nguyện để giá trị biểu thức \(l-f\) là nhỏ nhất có thể (Giang không muốn phải chi ra quá nhiều tiền so với Phương). Sẽ có \(q\) truy vấn dạng \(k_i\) \(m_i\) và bạn cần lập trình tính toán giá trị \(l-f\) nhỏ nhất với mỗi truy vấn này để Giang và Phương có thể chọn được một chiến lược mua tối ưu nhất nhé!

Input

Dòng đầu chứa hai số nguyên dương \(n\) và \(q\) \(\left(1\leq n,q\leq 10^5\right)\), lần lượt thể hiện số lượng bàn của nhà hàng Sen và số lượng màu sắc của những chiếc ghế.

Dòng tiếp theo chứa \(n\) số nguyên dương \(c_1\), \(c_2\),..., \(c_n\) \((1\leq c_i\leq 1000)\), với \(c_i\) là giá tiền của món hàng thứ \(i\).

Tiếp theo là \(q\) dòng, mỗi dòng chứa một cặp số nguyên dương \(k_i\) và \(m_i\) \(\left(1\leq k_i\leq 10^9, 1\leq m_i\leq n\right)\) mô tả một truy vấn.

Output

In ra \(q\) dòng. Dòng thứ \(i\) là một số nguyên thể hiện giá trị \(l-f\) nhỏ nhất trong truy vấn \(i\).

Ví dụ

Sample input 1

5 2
1 9 22 10 19
18 4
5 2

Sample output 1

34
-21

Giải thích

• Ở truy vấn đầu tiên, Giang và Phương có thể chọn mua các món hàng với giá tiền \(1\), \(9\), \(22\), và \(10\). Giá trị \(l-f\) tối ưu là \(38-4=34\).
• Ở truy vấn tiếp theo, Giang và Phương có thể chọn mua các món hàng với giá tiền \(22\), và \(9\). Giá trị \(l-f\) tối ưu là \(10-31=-21\).

Sample input 2

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

Sample output 2

4
16
7
1

Sample input 3

3 3
5 6 7
10 1
5 3
3 3

Sample output 3

5
12
0

Ràng buộc

• Subtask 1 (30 điểm): \(n,q\leq 1000\), \(c_i,k_i\leq 10^6\).
• Subtask 2 (30 điểm): \(k_1=k_2=...=k_n\).
• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.