Sau lần đổi quà trước, hkbao còn rất nhiều điểm thưởng nên quyết định thuyết phục thầy Phước để được đổi thêm quà tặng trafalgar_thu. Không riêng hkbao, nqtrieu cũng muốn lấy thêm quà để tặng 3T. Vì vậy cả hai cùng nhau đến nhà thầy.

Sau một hồi thuyết phục, cuối cùng thầy phước đã chấp nhận và lấy ra \(n\) món quà, cho phép hai bạn được đổi \(m\) món quà trong đó. Nhưng vì giá của mỗi món quà là khác nhau nên nqtrieu không biết làm thế nào để phân chia cho hợp lý thì hkbao đề xuất phương án sau:

Một phần quà bất kỳ có giá \(c\):

• Nếu \(c<k\), thì nqtrieu sẽ chi trả toàn bộ;
• Ngược lại, nqtrieu sẽ chỉ cần bỏ ra \(k\) điểm, và phần còn lại (tức \(c-k\)) sẽ do hkbao trả.

nqtrieu cảm thấy phương án đó không công bằng, nhưng lại không nghĩ ra cách nào hay hơn. Vì thế anh đã đưa ra yêu cầu rằng anh sẽ là người chọn ra \(m\) món quà để mua, và hkbao chấp nhận.

Ký hiệu \(T\) là tổng số điểm mà nqtrieu cần bỏ ra, và \(B\) là tổng số điểm mà hkbao phải bỏ ra. nqtrieu muốn chọn ra \(m\) món quà để đổi sao cho \(T\) nhỏ nhất có thể và \(B\) lớn nhất có thể, hay nói cách khác cần cực tiểu hóa (minimize) hiệu \(T-B\).

Nhưng vì không biết chính xác \(m\) món quà mà thầy Phước cho chọn cụ thể là bao nhiêu, và số \(k\) mà hkbao chọn là bao nhiêu nên nqtrieu đã đặt ra \(q\) giả định gồm các cặp \((k_i,\ m_i)\) và cần tính xem cực tiểu của \(T-B\) trong mỗi trường hợp là bao nhiêu. Vì số lượng giả định và số món quà rất lớn, lại không nhạy trong tính toán nên đành phải nhờ đến các bạn ITK21 giúp nqtrieu lần này rồi!

Input

• Dòng đầu chứa hai số nguyên dương \(n\) và \(q\) \((1\leq n,\ q\leq10^5)\), lần lượt là số lượng món quà và số giả định của nqtrieu;
• Dòng thứ hai chứa \(n\) số nguyên dương \(c_1,\ c_2,\ldots,\ c_n\) \((1\leq c_i\leq10^9,\forall i\in [1,\ n])\), thể hiện giá của các món quà tương ứng;
• Tiếp theo là \(q\) dòng, dòng thứ \(i\) chứa hai số nguyên dương \(k_i\) và \(m_i\) \((1\leq k_i\leq10^9,\ 1\leq m_i\leq n, \forall i\in [1,\ q])\).

Output

• In ra \(q\) dòng, trả lời cho \(q\) giả định.

Ví dụ

Sample input 1

5 3
7 10 8 14 5
10 3
9 3
7 4

Sample output 1

18
16
15

Sample input 2

6 2
7 25 15 10 19 13
14 6
9 4

Sample output 2

55
0

Ràng buộc

• Subtask 1 (25%): \(1\leq n,\ q\leq10^3;\ 1\leq c_i,\ k_i\leq10^6\);
• Subtask 2 (25%): \(k_1=k_2=\ldots=k_n\);
• Subtask 3 (50%): Không có ràng buộc gì thêm.