Laura và Fran đang thăm một nhà máy sản xuất sô cô la. Họ được tận mắt xem cách sô cô la được sản xuất, được ăn thử nhiều sô cô la rất ngon và bây giờ họ muốn mua một ít sô cô la về làm quà tại cửa hàng của nhà máy.

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

Fran đưa ra phương án trả tiền để mua ~m~ thanh sô cô la của hai bạn như sau:

• Nếu mua thanh sô cô la ~i~ có giá rẻ hơn ~k~ Euro thì Laura sẽ trả tiền là ~c_i~;
• Trái lại, nếu mua thanh sô cô la ~i~ có giá lớn hơn hoặc bằng ~k~ Euro, Laura sẽ trả ~k~ Euro và Fran sẽ trả phần còn lại là ~c_i - k~.

Gọi ~P~ là tổng số tiền Laura phải trả, ~F~ là tổng số tiền Fran phải trả để mua ~m~ thanh sô cô la. Laura không hài lòng với đề xuất của Fran, muốn chọc tức Fran nên chọn ~m~ thanh sô cô la để giá trị thể hiện của ~P - F~ là nhỏ nhất có thể.

Fran đưa ra ~q~ truy vấn, mỗi truy vấn cho biết 2 số ~k~ và ~m~. Fran do dự không biết nên mua những thanh sô cô la nào nên nhường quyền chọn sô cô la cho Laura. Trong lúc Fran đang do dự, Laura muốn nhanh chóng tìm ra giá trị nhỏ nhất của ~P - F~ tương ứng với mỗi truy vấn.

Hãy giúp cô Laura chọn sô cô la và tính giá trị nhỏ nhất của ~P - F~ tương ứng với mỗi truy vấn trong ~q~ truy vấn Fran đưa ra.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~q~ (~1 < n, q < 10^5~) tương ứng là số thanh sô cô la và số truy vấn;
• Dòng thứ 2 chứa ~n~ số nguyên không âm ~c_1, c_2, \dots, c_n~ tương ứng là giá của ~n~ thanh sô cô la;
• ~q~ dòng tiếp theo, mỗi dòng thứ ~i~ trong ~q~ dòng đó chứa 2 số nguyên ~k_i~ và ~m_i~ tương ứng là định mức để chia tiền mà Fran đưa ra và số lượng thanh sô cô la mà họ muốn mua trong truy vấn thứ ~i~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ ghi một giá trị tương ứng là giá trị nhỏ nhất của ~P - F~ tương ứng với truy vấn thứ ~i~ trong file input.