Aurora và Bianca rất thích bánh amaretti. Ông của họ vừa nướng một chồng bánh lớn. Hai người chia bánh bằng trò chơi sau. Khi chồng bánh vẫn còn bánh, họ lặp lại:

1. Aurora chọn một số nguyên \(X\ge0\).
2. Bianca chọn một số nguyên \(Y\ge0\) sao cho chồng còn ít nhất \(Y\) chiếc bánh và \(Y\ne X\).
3. Aurora ăn \(Y\) chiếc bánh trên cùng, hoặc không ăn chiếc nào nếu \(Y=0\).
4. Nếu vẫn còn bánh, Bianca ăn chiếc bánh trên cùng.

Mỗi chiếc bánh \(i\) có khối lượng \(W_i\). Khi hết bánh, mức hạnh phúc của mỗi người bằng tổng khối lượng bánh người đó đã ăn. Cả hai đều biết chiến thuật tối ưu và luôn chọn nước đi tối đa hóa mức hạnh phúc cuối cùng của chính mình.

Trong \(Q\) ngày tiếp theo, mỗi ngày ông làm một chồng mới có cùng số bánh. Cuối mỗi ngày trước ngày chơi tiếp theo, ông chỉ thay đổi khối lượng của một chiếc bánh; các chiếc khác giữ nguyên như ngày trước.

Hãy tính mức hạnh phúc cuối cùng của Bianca với chồng ban đầu và sau từng lần thay đổi.

Dữ liệu vào

Dòng đầu chứa \(N,Q\). Các bánh được đánh số từ \(0\) ở trên cùng đến \(N-1\) ở dưới cùng.

Dòng thứ hai chứa \(W_0,W_1,\ldots,W_{N-1}\).

Dòng thứ \(i\) trong \(Q\) dòng tiếp theo chứa \(P_i,Z_i\): khối lượng bánh \(P_i\) được đổi thành \(Z_i\).

Dữ liệu ra

In \(Q+1\) số nguyên: mức hạnh phúc của Bianca với chồng ban đầu rồi sau mỗi thay đổi.

Ràng buộc

• \(2\le N\le100\,000\).
• \(0\le Q\le100\,000\).
• \(1\le W_i\le50\).
• \(0\le P_i\le N-1\) và \(1\le Z_i\le50\).

Phân nhóm

1. \(8\) điểm: \(Q=0\) và mọi \(W_i=1\).
2. \(9\) điểm: \(N\le3\), \(Q\le5\).
3. \(11\) điểm: tại mọi thời điểm \(W_0\ge W_1\ge\cdots\ge W_{N-1}\).
4. \(13\) điểm: \(N\le100\), \(Q\le50\).
5. \(18\) điểm: \(N\le20\,000\), \(Q\le50\).
6. \(12\) điểm: \(N\le20\,000\), \(Q\le5000\).
7. \(29\) điểm: không có ràng buộc thêm.

Ví dụ

2 1
10 15
1 1

10
1

5 2
1 1 1 1 2
2 20
3 30

3
4
24

4 2
1 2 4 8
3 2
2 3

7
4
4

3 0
1 1 1

1

3 4
50 8 1
1 1
1 8
2 7
2 1

8
1
8
8
8

Nguồn

EGOI 2026 - Ngày 1, Biscuits.

Đề bài EGOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).