Minimum Fuel Consumption for Email Pickup Routing

In the "Feibeng" courier company, three drivers start their routes every day from fixed pickup points: 1, 2, and 3 respectively. The company has contracts with many small and medium enterprises and receives mail pickup registrations through their website. Each registration corresponds to a pickup point (an integer between 1 and m) and the registrations must be handled in the same order in which they are made.

The task is to partition the registration sequence into three ordered subsequences (one for each driver) so that the order for each driver is preserved. The cost for a driver assigned a route a = \(a_0, a_1, a_2, \dots, a_k\) is \(\sum_{i=1}^{k} D_{a_{i-1},a_i}\) where the starting position \(a_0\) is predetermined (1 for the first driver, 2 for the second, and 3 for the third). The cost matrix \(D\) is an \(m \times m\) matrix satisfying the triangle inequality such that for any \(i, j, k\): \[ D_{i,k} \le D_{i,j} + D_{j,k} \]

Your task is to compute the minimum total fuel consumption over all valid partitions of the registration sequence.

Note: Some drivers might not have any pickups on some days. Each driver, when assigned a new pickup, travels from his current location to the pickup point as determined by the registration order.

inputFormat

The input is given as follows:

1. An integer \(m\) representing the number of pickup points.
2. Then \(m\) lines follow, each containing \(m\) space‐separated integers. The \(j\)th number in the \(i\)th line represents \(D_{i,j}\) — the fuel cost from point \(i\) to point \(j\). It is guaranteed that \(D\) satisfies the triangle inequality.
3. An integer \(n\) representing the number of registrations (\(n \le 1000\)).
4. A line with \(n\) space‐separated integers \(s_1, s_2, \dots, s_n\) where each \(s_i\) (with \(1 \le s_i \le m\)) indicates the pickup point registered in the \(i\)th order.

outputFormat

Output a single integer — the minimum total fuel consumption required to complete the pickups according to the registration order.

sample

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

10