SERVICE - Mobile Service


A company provides service for its partners that are located in different towns. The company has three mobile service staff employees. If a request occurs at some location, an employee of the service staff must move from his current location to the location of the request (if no employee is there) in order to satisfy the request. Only one employee can move at any moment. They can move only on request and are not allowed to be at the same location. Moving an employee from location p to location q incurs a given cost C(p,q). The cost function is not necessarily symmetric, but the cost of not moving is 0, i.e. C(p,p)=0. The company must satisfy the received requests in a strict first-come, first-serve basis. The goal is to minimize the total cost of serving a given sequence of requests.

Task

You are to write a program that decides which employee of the service staff is to move for each request such that the total cost of serving the given sequence of requests is as small as possible.

Input

The first line of input contains the number of test cases - nTest. Each test case contains:

The first line of each test cases contains two integers, L and N. L (3 <= L <= 200) is the number of locations and N (1 <= N <= 1000) is the number of requests. Locations are identified by the integers from 1 to L. Each of the next L lines contains L non-negative integers. The jth number in the line i+1 is the cost C(i,j), and it is less than 2000.

The last of each test cases contains N integers, the list of the requests. A request is identified by the identifier of the location where the request occurs. Initially, the three service staff employees are located at location 1, 2 and 3, respectively.

Output

For each test case write the minimal total cost in a separate line.

Example

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
Output:
5

hide comments
Shubham Agrawal: 2018-06-05 22:07:57

One simple observation is what all needed. Convert the solution from NL^3 to NL^2.

kshubham02: 2017-11-29 10:32:05

Spent weeks but worth it :D
Some observations -
1. Although serving is FCFS, the company knows orders in advance and can plan accordingly (had it not been so, there would have been no point of the question, but still).
2. Thanks to @AAYUSH KUMAR, employee must move directly without using intermediate cities to reduce travelling cost.

hasan75: 2017-11-13 16:36:52

good one.... one good observation needs to make it O(NL^2) instead of O(NL^3) to pass the time limit :3

prasoonbatham: 2017-08-13 17:26:39

Try iterative dp. Wasted a lot of time reducing states in recursion + memoization. Coded in java.

shubham8_: 2017-06-14 05:36:03

Read the Question carefully, no two employee can be at same place, costed me few WA.
BTW nice question :)

devbishnoi: 2017-04-02 22:36:11

took whole day to AC, nice problem

newbie: 2015-08-29 15:15:44

finally AC :)

parijat bhatt: 2015-05-28 08:22:03

memoisation with a bit of symmetry :)

AAYUSH KUMAR: 2014-06-05 12:38:41

An employee must "directly" move from his current location to the location of request without using any intermediate locations to minimize the distance and will stay there till it moves to the location of any furthur request. It was not specified clearly and costed me few WA..

Last edit: 2014-06-05 15:52:52

Added by:Nguyen Dinh Tu
Date:2006-01-17
Time limit:2.448s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:CEOI 2005, Day 1