Một công ty cung cấp dịch vụ cho các đối tác của mình đặt tại ~n~ vùng khác nhau được đánh số 1, 2, 3, ..., ~n~. Công ty có 3 nhân viên phục vụ lưu động. Nếu xuất hiện yêu cầu tại một địa điểm mà hiện đang không có nhân viên đang ở đó, một trong ba nhân viên di chuyển từ vị trí tại của anh ta đến trực tiếp địa điểm xuất hiện yêu cầu mà không đi qua bất kỳ một địa điểm trung gian nào khác. Tại mọi thời điểm, chỉ có một nhân viên di chuyển. Các nhân viên chỉ di chuyển khi có yêu cầu phục vụ và không có hai nhân viên nào ở cùng một vị trí tại bất kỳ thời điểm. Chi phí để di chuyển từ vị trí ~i~ đến vị trí ~j~ là ~C_{ij}~. Chú ý rằng hàm chi phí không nhất thiết phải là đối xứng, tuy nhiên chi phí khi không di chuyển luôn bằng 0 (~C_{ii} = 0~). Các yêu cầu phải được thực hiện theo đúng thứ tự xuất hiện (yêu cầu xuất hiện trước phải được phục vụ trước, phục vụ xong một yêu cầu mới phục vụ yêu cầu tiếp theo).

Yêu cầu: Hãy tìm lịch di chuyển các nhân viên phục vụ yêu cầu sao cho tổng chi phí là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, m~, lần lượt là số vùng khác nhau và số yêu cầu cần phục vụ (~3 \le n \le 200, 1 \le m \le 1000~).
• ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên không âm có giá trị không vượt quá 2000. Số thứ ~j~ của dòng thứ ~i~ là giá trị của ~C_{ij}~ - chi phí để đi từ ~i~ đến ~j~.
• Dòng cuối cùng chứa ~m~ số nguyên là danh sách các yêu cầu phục vụ theo thứ tự đăng ký. Mỗi yêu cầu được mô tả bằng một số nguyên - số hiệu địa điểm, nơi yêu cầu xảy ra. Ban đầu ba nhân viên phục vụ đang ở các địa điểm 1, 2 và 3.

Output

• Ghi ra một số nguyên ~S~ là tổng chi phí nhỏ nhất tìm được.

Sample Input 1

5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1

Sample Output 1

5

Giải thích: Một phương án tối ưu là (1, 2, 1, 2, 2, 1, 3, 1, 3). Ở đây số thứ i là số hiệu của nhân viên phục vụ yêu cầu thứ i.

Subtasks

1. (35 điểm) ~3 \le n, m \le 8~
2. (30 điểm) ~8 < n, m \le 50~
3. (35 điểm) ~50 < n \le 200, 50 < m \le 1000~