Tô màu cây (Coloring Trees)

Nguồn: Codeforces

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

Đề bài

Có $n$ cây theo hàng, dùng $m$ màu. Một số cây đã có màu, số còn lại chưa tô. Tô cây $i$ màu $j$ tốn chi phí cho trước. Beauty là số đoạn màu liên tiếp tối đa. Hãy đạt beauty đúng $k$ với chi phí nhỏ nhất.

Input

Dòng đầu chứa $n,m,k$. Dòng hai chứa màu hiện tại của $n$ cây, 0 nếu chưa tô. Sau đó có $n$ dòng, mỗi dòng $m$ chi phí tô.

Output

In chi phí nhỏ nhất, hoặc -1 nếu không thể.

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

3 2 2
0 1 0
1 10
5 5
10 1

Output

2

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.