Oẳn tù tì (Hoof, Paper, Scissors)

Nguồn: USACO

Phiên bản: Phước Hưng OJ Extended

Đề bài

Bessie chơi $N$ ván Hoof-Paper-Scissors và biết trước nước của đối thủ. Bessie được đổi cử chỉ nhiều nhất $K$ lần. Hãy tối đa hóa số ván thắng.

Input

Dòng đầu chứa $N,K$. Dòng hai chứa $N$ số mã hóa đối thủ: 0=Hoof, 1=Scissors, 2=Paper.

Output

In số ván thắng lớn nhất.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

5 1
0 1 2 0 1

Output

3

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.