Treasure Hunt in the Divine Realm

You are given a divine realm partitioned into \(n\) regions, numbered from 1 to \(n\). There are \(n\) treasures hidden within these regions; the \(i\)-th treasure is located in region \(P_i\) (\(1\le P_i\le n\)). You are also given an \(n\times n\) distance matrix \(D\) where \(D[i][j]\) represents the distance from region \(i\) to region \(j\).

Your task is to help Copy, who starts his journey at region 1 and must leave the realm from region \(n\), by finding a route that collects all treasures while traveling the minimum total distance. A treasure in a region is collected when Copy visits that region. Note that Copy may visit regions without treasures, and even visit some regions more than once if necessary, in order to minimize the overall distance.

Input:

• The first line contains a single integer \(n\) representing the number of regions.
• The second line contains \(n\) integers \(P_1, P_2, \ldots, P_n\) indicating the region where each treasure is located.
• The next \(n\) lines each contain \(n\) integers. The \(j\)-th integer in the \(i\)-th line is \(D[i][j]\), the distance from region \(i\) to region \(j\).

Output: Output a single integer indicating the minimum distance Copy must travel to collect all treasures and reach region \(n\).

inputFormat

The input begins with an integer \(n\). The second line contains \(n\) space-separated integers \(P_1, P_2, \ldots, P_n\). This is followed by \(n\) lines, each containing \(n\) space-separated integers, which represent the distance matrix \(D\).

outputFormat

Output a single integer representing the minimum total distance required for Copy to start at region 1, collect all treasures, and finish at region \(n\).

sample

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

8