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 hai chị em thỏa thuận thì đưa ra quyết định:

- Nếu loại bút thứ \(i\) có giá tiền nhỏ hơn \(k\) đồng thì Lan sẽ trả tiền loại bút đó.

- Ngược lại, Lan sẽ trả \(k\) đồng, Thảo trả phần còn lại.

Nếu tổng số tiền Lan phải trả là \(l\) và Thảo phải trả là \(t\) cho \(m\) loại bút thì Lan sẽ chọn mua sao cho \(l - t\) bé nhất có thể.

Yêu cầu: Hãy cho biết, để chọn mua \(m\) loại bút và số tiền Lan muốn trả nhiều nhất là \(k\) trên mỗi loại thì \(l - t\ \)có giá trị nhỏ nhất là bao nhiêu?

Dữ liệu vào:

- Dòng đầu tiên gồm hai số nguyên \(n,\ q\ \left( 1 \leq n,q \leq 10^{5} \right)\ \)lần lượt là số loại bút và số lần Lan đề nghị mua.

- Dòng thứ \(2\) gồm \(n\ \)số nguyên \(a_{1},a_{2},..,a_{n}\) \(\left( 1 \leq a_{i} \leq 10^{9};\ 1 \leq i \leq n \right)\ \)là giá trị tương ứng của từng loại bút.

- \(q\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(k\ \)và \(m\) (\(1 \leq k \leq 10^{9};1 \leq m \leq n)\ \)lần lượt là giới hạn số tiền Lan trả và số loại bút cần mua.

Kết quả:

- Kết quả ghi trên \(q\) dòng. Dòng thứ \(i\) là câu trả lời cho đề nghị thứ \(i\) của Lan.

Ví dụ:

Giải thích:

Trong đề nghị đầu tiên, Lan có thể mua 3 loại bút có giá \(1;\ 6\) và \(25\) đồng, khi đó Lan sẽ trả \(22\) đồng và Thảo trả \(10\) đồng. Câu trả lời là \(22 - 10 = 12\).

Trong đề nghị thứ hai, Lan sẽ chọn mua 2 loại bút có giá \(20\ \)và \(25\) đồng, khi đó Lan sẽ trả \(10\) đồng và Thảo trả \(35\) đồng. Câu trả lời là \(10 - 35 = - 25\).

Ràng buộc dữ liệu:

- Có \(50\%\) số test ứng với \(1 \leq n,q \leq 1000;{1 \leq a}_{i},k_{i} \leq 10^{6}.\)

- Có \(50\%\) số test không có ràng buộc gì thêm.