Coloring Trees

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

This package preserves the original task mechanism. 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ể.

Subtasks

• Subtask 1 — 20 points: small data.
• Subtask 2 — 30 points: medium data.
• Subtask 3 — 50 points: full PHOJ package limits.

Examples

Input

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

Output

2

Explanation

The output follows directly from the rules above.