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 đổi dãy bánh ban đầu 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ả chi phí \(C_{i,1}, C_{i,2}, \dots, C_{i,T}\) (\(C_{i,j} \le 10^6\)).
• Dòng cuối cùng chứa \(N\) số tự nhiên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le T\)) thể hiện loại bánh của từng chiếc bánh tại vị trí thứ \(i\).

Output

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

Example

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

2