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.
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, 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 cho phép anh ấy giải tối đa ~c_i~ bài tập. 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
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~,
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~,
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~,
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~.
Comments