Alice có \(N\) chiếc bánh, mỗi chiếc thuộc một trong \(T\) loại được xếp thành một hàng. Một dây bánh được gọi là đẹp nếu mỗi chuỗi bánh liên tiếp cùng loại có độ dài tối thiểu là \(K\). Từ dây bánh ban đầu, Alice muốn thay đổi loại bánh ở một số vị trí sao cho dây bánh trở thành dây bánh đẹp.

Với mỗi vị trí, Alice có thể thay đổi loại bánh, biết rằng chi phí mỗi lần thay đổi từ loại bánh \(i\) (\(1 \le i \le T\)) thành loại bánh \(j\) (\(1 \le j \le T\)) là \(C_{i,j}\).

Yêu cầu:

• Hãy tìm chi phí nhỏ nhất để biến dãy thành dãy bánh đẹp.

Input

• Dòng đầu tiên gồm ba số tự nhiên \(N, T, K\) (\(1 \le N, K \le 10^5;\ 1 \le T \le 100\)).
• \(T\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le T\)) gồm \(T\) số nguyên không âm mô tả dãy \(C_{i,1}, C_{i,2}, ..., C_{i,T}\) (\(C_{i,j} \le 10^6\)).
• Dòng cuối cùng chứa \(N\) số tự nhiên, số thứ \(j\) (\(1 \le j \le N\)) chứa số nguyên dương \(A_j\) (\(1 \le A_i \le T\)) thể hiện loại bánh của chiếc bánh thứ \(i\).

Output

• Gồm một dòng chứa một số là chi phí nhỏ nhất Alice để đổi bánh.

Input 1

5 2 2
0 5
1 0
1 2 2 1 1

Output 1

2

Giải thích

• Đổi hai bánh ở vị trí 2 và 3 từ loại 2 thành loại 1 mất chi phí bằng 2.

Subtask 1 (20%): \(N, K \le 100;\ T \le 20\)

Subtask 2 (20%): \(K = 2\)

Subtask 3 (30%): \(N, K \le 500\)

Subtask 4 (30%): Không có ràng buộc nào thêm.