Vào năm ~2069~, để khuyến khích các thành đua top điểm, VNOJ đã tổ chức event trong ~q~ ngày: vào ngày thứ ~i~, với mỗi ~k_i~ bài tập giải được, user sẽ được gấp đôi số điểm cho bài tập thứ ~k_i + 1~ (bài tập này sẽ không tính vào ~k_i~ bài tập tiếp theo). Lúc này, hệ thống VNOJ có ~n~ bài tập, bài tập thứ ~i~ nếu giải đúng sẽ được ~p_i~ điểm.

lastPledge quyết định làm bài trên VNOJ để giải trí sau những giờ chơi game căng thẳng. Tuy nhiên vì đang bận leo rank LMHT, lastPledge chỉ có thể chọn ~1~ trong ~q~ ngày để leo rank VNOJ. Biết rằng vào ngày thứ ~i~, tâm trạng của lastPledge cho phép anh ấy giải tối đa ~c_i~ bài tập. lastPledge muốn tính xem làm bài vào ngày nào thì sẽ được nhiều điểm nhất, vì vậy anh ấy muốn biết: nếu giải bài vào ngày thứ ~i~, anh ấy sẽ nhận được tối đa bao nhiêu điểm.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~ (~1 \le n \le 10^6~) – số bài tập trên VNOJ và ~q~ (~1 \le q \le 10^6~) - số ngày diễn ra event trên VNOJ.

Dòng thứ hai gồm ~n~ số nguyên dương ~p_1, p_2, \ldots, p_n~ ~(1 \le p_i \le 10^9)~ – số điểm nhận được nếu giải bài thứ ~i~.

~q~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~c_i~ và ~k_i~ (~1 \le c_i, k_i \le n~) thể hiện ngày thứ ~i~ của event trong đề bài.

Output

Gồm ~q~ dòng, dòng thứ ~i~ in ra số điểm tối đa lastPledge nhận được nếu giải bài vào ngày thứ ~i~.

Subtask

• ~50\%~ số test có ~n \le 10^3~.

• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5 3
4 7 6 5 3
4 2
5 1
3 3

Sample Output 1

29
38
18

Notes

Vào ngày thứ ~1~, lastPledge có thể chọn giải bài theo thứ tự ~[3, 1, 2, 4]~. Số điểm anh ấy nhận được là ~6 + 4 + 7 \cdot 2 + 5 = 29~.

Vào ngày thứ ~2~, lastPledge có thể chọn giải bài theo thứ tự ~[4, 3, 5, 2, 1]~. Số điểm anh ấy nhận được là ~5 + 6 \cdot 2 + 3 + 7 \cdot 2 + 4 = 38~.

Vào ngày thứ ~3~, lastPledge có thể chọn giải bài theo thứ tự ~[3, 4, 2]~. Số điểm anh ấy nhận được là ~6 + 5 + 7 = 18~.