Fran ban đầu có một dải giấy dài \(n\) cm. Lana đưa ra \(k\) chỉ dẫn dạng: cắt dải thứ \(x\) tại vị trí cách đầu trái \(l\) cm. Nếu hiện có dãy độ dài \(a_1,a_2,\ldots,a_m\), sau chỉ dẫn này dải \(a_x\) được thay trong dãy bằng hai dải có độ dài \(l\) và \(a_x-l\); thứ tự của các dải còn lại không đổi. Sau khi thực hiện hết các lần cắt, hãy tính có bao nhiêu độ dài dải giấy khác nhau còn lại.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,k\) (\(2\le n\le500\), \(1\le k<n\)), lần lượt là độ dài ban đầu và số chỉ dẫn. Dòng thứ \(i\) trong \(k\) dòng sau chứa \(x_i,l_i\) (\(1\le x_i\le i\), \(1\le l_i<L\)), trong đó \(L\) là độ dài của dải thứ \(x_i\) ngay trước lần cắt thứ \(i\); các dải được đánh số từ trái sang phải trong dãy hiện thời.

Dữ liệu ra

In một số nguyên: số độ dài dải giấy khác nhau sau mọi lần cắt.

Ràng buộc

Các giới hạn chính thức được nêu trong phần Dữ liệu vào.

Phân nhóm

1. \(9\) điểm: \(k\le3\).
2. \(6\) điểm: \(l_i=1\) với mọi \(i\).
3. \(13\) điểm: \(x_i=i\) với mọi \(i\).
4. \(22\) điểm: không có ràng buộc thêm.

Ví dụ

5 1
1 2

2

6 2
1 4
1 2

1

10 3
1 2
2 3
3 2

2

Nguồn

COCI 2025/2026 - Vòng 5, bài Škare.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.