Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2899
Hangzhou Tour

Time Limit: 5 Seconds      Memory Limit: 32768 KB

My best friend in high school, Mike, comes to Hangzhou. But since I have to join the Algorithm Contests Month(ACM), I can't be the guide as I promised. At least one thing I can do is to help him arrange a tour to see all the N sights that he would like to view.

We label the N sights by 1,2,...,N and where we live now, ZJG, is labelled by 0.

Mike refuses to take the tour by bus because of his carsickness. But it would be a disaster to take all roads on foot, so I will lend him my bike.

Here is our tour plan. Mike will leave ZJG in the morning, take the sightseeing on N sights(each at least once), and be back to ZJG sometime in the evening. And he wonders how long will it take to finish the sightseeing. So this is our job.

Notice that Mike will leave with my bike and be back with it! It will drive me crazy if he leaves the bike somewhere out of the school.

There are two kinds of roads between every locations.(0,1,...,N) The first kind of road on which you could either ride a bike or walk on foot, while you could only walk on foot on the second kind of road. Note that going by bike is much faster than on foot. And once you choose to walk on foot, you have to leave the bike on the sight and come back to get it some time later.

Input

The first line of input is an integer N.( 0 < N <= 12 )

The second line contains N positive integers representing the time that Mike will stay on the ith sight on his first visiting.

From the 3rd line to (N+3)th line, each contains N+1 non-negetive integers. These integers form a (N+1)*(N+1) matrix, F. If Fij = 0 then there is NO direct path from i to j on foot, else Fij is the time from i to j on foot. And for all 0 <= i,j <= N, Fij = Fji.

From the (N+4)th line to (2*N+4)th line, each contains N+1 non-negetive integers. These integers form a (N+1)*(N+1) matrix, B. If Bij = 0, then there is NO direct path from i to j by bike, else Bij is the time from i to j by bike. And for all 0 <= i,j <= N, Bij = Bji.

All the times mentioned above is less than 1000.

There will be several test cases. Process to the end-of-file.

Output

There will be only one line for each test case containing the minimum time.

Sample Input

4
44 52 60 51
0 15 0 0 24
15 0 20 30 30
0 20 0 20 15
0 30 20 0 10
24 30 15 10 0
0 5 0 0 8
5 0 0 0 10
0 0 0 0 0
0 0 0 0 0
8 10 0 0 0

Sample Output

275

Hint

Mike will take the route like this: 0 - 1 - 4 - 2 - 3 - 4 - 0. After first visiting on 4, he will leave the bike there and walk to 2 and 3. Then he will come back to 4 to get the bike and ride to 0 to finish the tour day.

Author: GAO, Fei
Source: ZOJ Monthly, January 2008
Submit    Status