~A~ và ~B~ là hai người chơi vào vòng chung kết một cuộc thi và được nhận các phần thưởng do công ty ~\mathrm{AZ}~ tài trợ. Vòng chung kết sẽ diễn ra trong ~M~ ngày. Ban đầu, ban tổ chức sẽ chuẩn bị trước ~N~ món quà. Các phần quà được đánh số từ ~1~ đến ~N~, phần quà thứ ~i~ từ trái sang phải có giá trị là ~a_{i}~. Mỗi ngày thi sẽ diễn ra như sau, ban tổ chức sẽ chọn ra một phần quà, và thay thế nó bằng một phần quà mới. Cụ thể hơn, vào ngày thứ ~i~, ban tổ chức sẽ chọn ra hai số ~x_{i}, v_{i}~ và thay phần quà ở vị trí ~x_{i}~ thành một phần quà mới có giá trị là ~v_{i}~. Sau đó, ~A~ và ~B~ sẽ luân phiên nhau chọn quà. ~A~ đi trước và cả hai người đều muốn tối ưu tổng giá trị của các phần quà mình nhận được.

Yêu cầu: Tính xem ở mỗi ngày chơi, ~A~ sẽ nhận được tối đa tổng giá trị của các phần quà là bao nhiêu nếu cả ~A~ và ~B~ đều chơi tối ưu.

Dữ liệu:

• Dòng thứ nhất chứa hai số nguyên dương ~N, M\left(1 \leq N, M \leq 10^{5}\right)~;
• Dòng thứ hai chứa ~N~ số nguyên dương, số thứ ~i~ là ~a_{i}\left(1 \leq a_{i} \leq 10^{6} ; i=1,2, \ldots, N\right)~;
• Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa hai số nguyên dương ~x_{i}, v_{i}\left(1 \leq x_{i} \leq N ; 1 \leq\right.~ ~\left.v_{i} \leq 10^{6}\right)~.

Kết quả:

• Ghi ra trên ~M~ dòng, dòng thứ ~i~ là tổng giá trị các phần quà mà ~A~ nhận được ở ngày thứ ~i~.

Ví dụ:

Sample Input

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

Sample Output

8

12

11

Giải thích:

• Ngày thứ nhất, các phần quà có giá trị là ~1,5,4,1,2~. ~A~ có thể lấy được các phần quà có tổng giá trị là ~1+5+2=8~.
• Ngày thứ hai, các phần quà có giá trị là ~7,5,4,1,2~. ~A~ có thể lấy được các phần quà có tổng giá trị là ~7+4+1=12~.
• Ngày thứ ba, các phần quà có giá trị là ~7,3,4,1,2~. ~A~ có thể lấy được các phần quà có tổng giá trị là ~7+3+1=11~.

Chấm điểm:

• Subtask 1 (~40\%~): ~N, M \leq 10^{3}~;
• Subtask 2 (~30\%~): ~a_{i}, v_{j} \leq 100(i=1,2, \ldots, N ; j=1,2, \ldots, M)~;
• Subtask 3 (~30\%~): Không có thời điểm nào tồn tại hai món quà có cùng giá trị.