Phục vụ

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,\dots ,n$. Công ty có $3$ nhân viên phục vụ lưu động. Nếu xuất hiện một yêu cầu tại một địa điểm mà hiện đang không có nhân viên nào ở đó, một trong ba nhân viên di chuyển từ vị trí hiện 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 qua bất kỳ một địa điểm trung gian nào khác. Nếu đã có nhân viên ở địa điểm xuất hiện yêu cầu thì không ai di chuyển. 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 nào. 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).

Ban đầu ba nhân viên phục vụ đang ở các địa điểm $1$, $2$ và $3$.

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.

Dữ liệu vào

• 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 là số hiệu địa điểm nơi yêu cầu xảy ra.

Dữ liệu ra

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

Ràng buộc

• $3\le n\le 200$, $1\le m\le 1000$.
• $0\le C_{ij}\le 2000$, $C_{ii}=0$.
• Mỗi yêu cầu là một số nguyên trong đoạn $[1,n]$.

Subtasks

• Subtask 1 ($35\%$ số điểm): $3\le n,m\le 8$.
• Subtask 2 ($30\%$ số điểm): $n,m\le 50$.
• Subtask 3 ($35\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ