Hai chị em Lan và Thảo cùng đến nhà sách chuẩn bị mua đồ dùng học tập cho năm học mới. Nhà sách hiện tại có \(n\) loại bút khác nhau được đánh số từ \(1\) tới \(n\).

Hai chị em dự định cùng nhau mua \(m\) loại bút (mỗi loại một cây), loại bút thứ \(i\) có giá \(a_i\) đồng. Sau khi thỏa thuận, họ quyết định:

• Nếu loại bút thứ \(i\) có giá nhỏ hơn \(k\) đồng, Lan sẽ trả toàn bộ số tiền.
• Nếu giá lớn hơn hoặc bằng \(k\), thì Lan sẽ trả \(k\) đồng, phần còn lại Thảo trả.

Mục tiêu:

Với một đề nghị cụ thể gồm \(k\) (giới hạn Lan muốn trả tối đa cho mỗi loại bút) và \(m\) (số loại cần mua), Lan sẽ chọn \(m\) loại bút sao cho \(l - t\) là nhỏ nhất, trong đó:

• \(l\) là tổng tiền Lan trả,
• \(t\) là tổng tiền Thảo trả.

Yêu cầu:

• Với mỗi đề nghị, hãy tính giá trị nhỏ nhất của \(l - t\) khi Lan chọn \(m\) loại bút phù hợp với tiêu chí trên.

Dữ liệu vào:

• Dòng đầu gồm hai số nguyên \(n\), \(q\) (\(1 \le n, q \le 10^5\)) — số loại bút và số đề nghị.
• Dòng thứ hai gồm \(n\) số nguyên \(a₁, a₂, ..., aₙ\) (\(1 \le a_i \le 10^9\)) — giá của từng loại bút.
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(k\) và \(m\) (\(1 \le k \le 10^9\), \(1 \le m \le n\)).

Dữ liệu ra:

• In ra \(q\) dòng, mỗi dòng là câu trả lời tương ứng với một đề nghị.

Input 1

7 2
1 8 7 20 25 18 6
15 3
5 2

Output 1

12
-25

Giải thích:

• Đề nghị 1 (k = 15, m = 3):
  Chọn 3 loại bút giá 1, 6, 25 → Lan trả: 1 + 6 + 15 = 22; Thảo trả: 25 - 15 = 10
  ⇒ \(l - t = 22 - 10 = 12\)
• Đề nghị 2 (k = 5, m = 2):
  Chọn 20 và 25 → Lan trả: 5 + 5 = 10; Thảo trả: 15 + 20 = 35
  ⇒ \(l - t = 10 - 35 = -25\)

Ràng buộc:

• Có 50% số test ứng với \(1 \le n, q \le 1000\), \(1 \le a_i, k_i \le 10^6\).
• Có 50% số test còn lại không có ràng buộc gì thêm.