Trò chơi thả bóng được chơi trên một bảng gồm \(P\) block, mỗi block gồm \(M\) hàng và \(N\) cột (bảng lặp lại \(P\) lần). Các hàng được đánh số từ \(1\) đến \(P \times M\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(N\) từ trái sang phải. Ô ở hàng \(i\), cột \(j\) được gọi là ô \((i, j)\).

Ở mỗi ô của bảng, có vách ngăn chéo chạy theo một trong hai hướng: trên trái xuống dưới phải, hoặc trên phải xuống dưới trái.

Nếu bạn thả quả bóng ở một cột \(X\) nào đó, theo trọng lực quả bóng sẽ rơi xuống dưới. Quả bóng sẽ không thể đi xuyên các vách ngăn nên sẽ xảy ra các trường hợp sau:

• Quả bóng bị kẹt ở trong bảng và không thể di chuyển nữa.
• Quả bóng rơi ra ngoài bảng ở cạnh bên trái.
• Quả bóng rơi ra ngoài bảng ở cạnh bên phải.
• Quả bóng rơi ra ngoài bảng ở đáy của bảng ở cột \(Y\).

Nếu trường hợp \(1\) đến \(3\) xảy ra, ta gọi \(f(X) = -1\), nếu trường hợp cuối xảy ra ta gọi \(f(X) = Y\).

Ví dụ nếu ta thả quả bóng ở cột \(4\) thì quả bóng sẽ rơi ra ngoài ở cạnh bên phải.

Nếu chúng ta thả quả bóng ở cột \(1\) thì quả bóng sẽ rơi ra ngoài bảng ở cột \(3\).

Ngoài ra, chúng ta có thể thực hiện phép thay đổi chiều vách ngăn với các ô trên bảng. Ví dụ sau đây là bảng sau khi ta thực hiện phép thay đổi với ô \((4, 2)\). Phép thay đổi ở ô \((4, 2)\) sẽ có chi phí là \(cost_{4, 2}\):

Bây giờ, nếu chúng ta thả quả bóng ở cột \(1\) thì quả bóng sẽ rơi ra ngoài bảng ở cột \(1\).

Trong bài toán này, cho cấu hình bảng ban đầu, chi phí thay đổi vách ngăn, \(k\) là số lượng quả bóng sẽ được thả, mảng \(start\) gồm \(K\) phần tử là chỉ số các cột sẽ thả bóng, mảng \(target\) gồm \(K\) phần tử là giá trị \(f(start_{1}), f(start_{2}), \ldots, f(start_{K})\). Bạn có thể thực hiện một số phép đổi chiều vách ngăn, sau đó thả lần lượt quả bóng. Hãy tính chi phí tối thiểu để đạt được kết quả mong muốn.

Input

• Dòng thứ nhất ghi ba số \(P, M\) và \(N\) \((1 \leq P \leq 10^{6}, 1 \leq M \leq 1000, 1 \leq N \leq 10)\).
• Tiếp theo là \(M\) dòng, mỗi dòng ghi xâu \(N\) kí tự để mô tả \(1\) block của bảng ban đầu. Các xâu chỉ chứa các kí tự \ tương ứng với vách ngăn từ trái trên xuống phải dưới hoặc / tương ứng với vách ngăn từ phải trên xuống trái dưới.
• Tiếp theo là \(M\) dòng, mỗi dòng ghi \(M\) số nguyên dương, mô tả chi phí thay đổi vách ngăn của các ô \((1 \leq cost_{i, j} \leq 10^{6})\).
• Dòng tiếp theo chỉ chứa duy nhất số \(K\) \((1 \leq K \leq N)\).
• Dòng tiếp theo ghi \(K\) số có giá trị tăng dần \(start_{1}, start_{2}, \ldots, start_{K}\) \((1 \leq start_{i} \leq N)\).
• Dòng cuối cùng ghi \(K\) số \(target_{1}, target_{2}, \ldots, target_{K}\) \((1 \leq target_{i} \leq N\) hoặc \(target_{i} = -1)\).

Output

• In ra một số nguyên đuy nhất là chi phí tối thiểu tìm được.

Scoring

• Subtask \(1\) (\(16\%\) số điểm): \(P = 1, M \times N \leq 20\).
• Subtask \(2\) (\(16\%\) số điểm): \(P \leq 10, K = 1\).
• Subtask \(3\) (\(16\%\) số điểm): \(P \leq 10, K = 2\).
• Subtask \(4\) (\(16\%\) số điểm): \(P \leq 10\).
• Subtask \(5\) (\(36\%\) số điểm): không có rằng buộc gì thêm.

Example

1 4 4
\\\\
////
\\\\
/\\\
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
2
1 4
1 -1

1

2 4 4
\\\\
////
\\\\
/\\\
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
2
1 4
1 4

5