Lana và Fran là đôi bạn thân rất thích Socola. Hai bạn vào một đại lý bán Socola, hiện tại, đại lý có ~n~ loại có giá lần lượt là ~c_1, c_2, ..., c_n~ (~1 \le c_i \le 10^9~) đồng. Hai bạn muốn mua đúng ~m~ loại (~m~ gói, mỗi loại 1 gói). Cách trả tiền của hai bạn rất đặc biệt như sau:

• Nếu giá của gói socola nhỏ hơn ~k~ (đồng) thì Lana sẽ trả gói đó.
• Ngược lại (giá lớn hơn hoặc bằng ~k~), Lana sẽ trả ~k~ đồng, phần còn lại Fran sẽ trả.

Cho biết ~k~, gọi ~L~ là số tiền Lana phải trả, ~F~ là số tiền Fran phải trả. Hãy giúp hai bạn chọn ~m~ loại socola để mua sao cho hiệu ~L - F~ đạt giá trị nhỏ nhất.

Input Socola.Inp

• Dòng 1 ghi 2 số nguyên dương ~n~ và ~q~ (~n, q \le 10^5~) tương ứng là số loại socola và số truy vấn.
• Dòng 2 ghi ~n~ số nguyên dương ~c_1, c_2, ..., c_n~ (~1 \le c_i \le 10^9~) tương ứng là giá của ~n~ loại socola.
• ~q~ dòng cuối, mỗi dòng ghi hai số nguyên dương ~k~ và ~m~ (~1 \le m \le n; 1 \le k \le 10^9~).

Output Socola.Out

Gồm ~q~ dòng, mỗi dòng là giá trị nhỏ nhất của hiệu ~L - F~ ứng với mỗi truy vấn.

Giới hạn

• Sub1: ~n, q \le 1000~; ~c_i, k \le 10^6~.
• Sub2: Tất cả các truy vấn có cùng giá trị ~k~.
• Sub3: Không có giới hạn gì thêm.

Ví dụ

Socola.Inp

5 2
1 9 22 10 19
18 4
5 2

Socola.Out

34
-21

Giải thích

• Query ~1 (k=18, m=4)~: Chọn: ~1, 9, 10~ (Lana trả hết) và ~22~ (Lana ~18~, Fran ~4~). ~L = 1+9+10+18 = 38~. ~F = 4~. Hiệu ~= 34~.
• Query ~2 (k=5, m=2)~: Chọn: ~22, 19~ (Lana trả ~5+5=10~, Fran trả ~17+14=31~). ~L = 10~, ~F = 31~. Hiệu ~= -21~.