Hai bạn nhỏ Lana và Fran đến thăm một nhà máy sản xuất sô-cô-la. Họ đã thấy cách làm sô-cô-la, nếm thử nhiều loại sô-cô-la và giờ họ muốn mua một số sô-cô-la mang về làm quà cho các bạn ở lớp.

Trong cửa hàng, có ~n~ loại sô-cô-la khác nhau và loại thứ ~i~ có giá là ~c_i~. Lana và Fran muốn mua ~m~ loại sô-cô-la.

Fran đã đưa ra cách chia tiền mua sô-cô-la cho 2 bạn như sau:

• Nếu mua loại sô-cô-la có giá rẻ hơn ~k~ Đô la, Lana sẽ trả tiền.
• Nếu không, Lana sẽ trả ~k~ Đô la và Fran sẽ trả phần còn lại, tức là ~c_i - k~ Đô la.

Gọi ~L~ là số tiền Lana phải trả, và ~F~ là số tiền Fran phải trả. Lana, không hài lòng với thỏa thuận của Fran, muốn làm Fran tức giận nên cô ấy muốn chọn sô-cô-la sao cho giá trị của biểu thức ~L - F~ càng nhỏ càng tốt. Lana muốn biết giá trị tối thiểu của biểu thức ~L - F~ với ~q~ truy vấn khác nhau, mỗi truy vấn bao gồm 2 số ~k_i~ và ~m_i~.

Yêu cầu: Hãy giúp cô ấy chọn sô-cô-la và xác định giá trị tối thiểu của biểu thức ~L - F~ với mỗi truy vấn.

Input

• Dòng đầu chứa 2 số nguyên ~n~ và ~q~ (~1 \le n, q \le 10^5~) tương ứng là số lượng loại sô-cô-la và số lượng truy vấn.
• Dòng thứ 2 chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~ (~1 \le c_i \le 10^9~) theo thứ tự là giá của từng loại sô-cô-la.
• ~q~ dòng sau, mỗi dòng chứa 2 số ~k_i~ và ~m_i~ (~1 \le k_i \le 10^9, 1 \le m_i \le n~) tương ứng là giới hạn ~k~ mà Fran đưa ra và số lượng sô-cô-la mà họ sẽ mua.

Output

• In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Sample Input 1

5 2
1 9 22 10 19
18 4
5 2

Sample Output 1

34
-21