Ba nhân viên phục vụ

Một công ty có ba nhân viên lưu động cùng phục vụ khách hàng ở \(L\) địa điểm, đánh số từ \(1\) đến \(L\). Lúc đầu ba nhân viên đứng ở các địa điểm \(1\), \(2\) và \(3\).

Công ty lần lượt nhận \(N\) yêu cầu, mỗi yêu cầu xuất hiện tại một địa điểm và phải được xử lý đúng theo thứ tự đến. Khi có yêu cầu tại địa điểm \(x\):

• nếu đã có một nhân viên đứng ở \(x\) thì không ai phải di chuyển (chi phí \(0\));
• ngược lại đúng một nhân viên phải đi từ vị trí hiện tại \(p\) đến \(x\) và tốn chi phí \(C(p, x)\).

Mỗi lúc chỉ một nhân viên được di chuyển, chỉ di chuyển khi có yêu cầu, và hai nhân viên không bao giờ được đứng cùng một địa điểm. Chi phí có thể không đối xứng (\(C(p,q) \ne C(q,p)\)) và \(C(p,p)=0\).

Hãy chọn nhân viên cho từng yêu cầu sao cho tổng chi phí nhỏ nhất, và in ra tổng đó.

Input

• Dòng đầu chứa số bộ dữ liệu \(nTest\).
• Mỗi bộ dữ liệu gồm:
• một dòng hai số nguyên \(L\) và \(N\);
• \(L\) dòng, mỗi dòng \(L\) số nguyên không âm; số thứ \(j\) của dòng thứ \(i\) là \(C(i, j)\);
• một dòng \(N\) số nguyên là các địa điểm yêu cầu, theo thứ tự.

Output

Với mỗi bộ dữ liệu in ra một dòng chứa tổng chi phí nhỏ nhất.

Constraints

• \(1 \le nTest \le 10\)
• \(3 \le L \le 200\)
• \(1 \le N \le 500\)
• \(0 \le C(i,j) \le 2000\)

Sample Input

1
4 6
0 3 2 5
4 0 1 2
2 6 0 1
3 2 4 0
4 4 2 1 4 3

Sample Output

2

Explanation

Yêu cầu đầu ở địa điểm \(4\): nhân viên ở \(3\) đi sang \(4\), tốn \(C(3,4)=1\) (ba nhân viên ở \(1,2,4\)). Các yêu cầu ở \(4\), \(2\), \(1\), \(4\) đều đã có người nên tốn \(0\). Yêu cầu cuối ở \(3\): nhân viên ở \(2\) đi sang \(3\), tốn \(C(2,3)=1\). Tổng cộng \(2\).