Giao hàng

Khu Trang ở có \(N\) ngôi nhà đánh số từ \(1\) đến \(N\), các ngôi nhà được nối với nhau bởi các con đường. Từ một ngôi nhà bất kỳ sang một ngôi nhà khác luôn có một và chỉ một con đường một chiều, độ dài các con đường có thể không giống nhau. Nhà Trang là ngôi nhà số \(1\). Một ngày nọ, Trang nhận được đơn đặt hàng của \(K\) ngôi nhà khác, Trang cần tìm ra lộ trình, xuất phát từ nhà, đi tới các ngôi nhà để giao hàng, và quay trở về nhà; sao cho tổng độ dài đường đi là nhỏ nhất.

Do điều kiện khó khăn, Trang chỉ mua được Ipod, Itouch, Iphone, Ipad, Iwatch mà chưa đủ tiền mua MacBook. Vì vậy, Trang cần sự giúp đỡ của các bạn để tìm ra độ dài đường đi ngắn nhất. Các bạn hãy giúp Trang nhé!

Input

Dòng đầu tiên chứa số nguyên \(N\) là số ngôi nhà, và số nguyên \(K\) là số ngôi nhà có đơn đặt hàng. \((2 ≤ N ≤500,1 ≤ K < N)\)

\(N\) dòng tiếp theo, mỗi dòng gồm \(N\) số nguyên. Số thứ \(j\) trong dòng thứ \(i\) (ký hiệu \(c_{i, j}\)) là độ dài đường đi từ ngôi nhà \(i\) tới ngôi nhà \(j\). \((0 ≤ c_{i,j} ≤ 10^8\), \(c_{i,i} = 0\)).

Dòng cuối cùng chứa \(K\) số nguyên phân biệt là \(K\) ngôi nhà có đơn đặt hàng. Ngôi nhà số \(1\)
không có đơn đặt hàng.

Output

In ra một số nguyên duy nhất là độ dài lộ trình nhỏ nhất tìm được.

Example

5 3
0 6 10 8 7
10 0 9 7 9
9 9 0 10 7
8 10 9 0 8
7 9 9 7 0
4 5 2

28