Long Night of Museums

Interview

Time limit1sMemory limit128 MB

Summary

With at most 20 museums, viewing times, and travel times, find the largest number of distinct museums a 420-minute tour can include.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Graph, Brute force
Solved: No attempts yet

Problem

Vienna, Austria is called the "City of Culture", partly because it has more than 100 museums within the city. There are so many museums that visiting all of them is difficult and expensive, no matter how long you stay. Fortunately, there is a special night called the "Long Night of Museums", when a single ticket lets you visit many museums from 6:00 pm until 1:00 am the next day.

Even so, you cannot visit every museum in the city, for two reasons. First, some museums close at 5:00 pm and do not take part in the event. Second, the 7 hours are not enough to travel to every museum, view each one completely, and then move on to the next.

You are given the number of participating museums, the time needed to view the inside of each museum, and the time needed to travel from each museum to every other. Find a tour that visits as many museums as possible during the Long Night of Museums, and report the maximum number of museums you can visit.

You may start at any museum (no travel time is spent reaching the first one), and your tour visits distinct museums one after another. The total time available is 7 hours (420 minutes), from 6:00 pm to 1:00 am. Along the chosen route, the sum of the viewing times of the visited museums plus the sum of the travel times between consecutive museums must not exceed 420 minutes.

Input

The input contains several test cases. The first line of a test case contains one integer $N$ , the number of museums participating in the event ( $1 \le N \le 20$ ). Each museum has a unique identification number from $1$ to $N$ . The second line contains $N$ integers giving the time, in minutes, needed to view each museum from $1$ to $N$ . Then follow $N$ lines describing the travel times. The $i$ -th of these lines contains $N$ integers $M_{i,1}, M_{i,2}, \dots, M_{i,N}$ , where $M_{i,k}$ is the time, in minutes, to travel from museum $i$ to museum $k$ . The $i$ -th integer on the $i$ -th line (that is, $M_{i,i}$ ) is always $0$ . The end of input is indicated by $N = 0$ .

Output

For each test case, print one line containing the maximum number of museums that can be visited during the Long Night of Museums.

Examples3

Example 1

Input

Expected output

0
1
2

Example 2

Input

3
100 100 100
0 60 999
999 0 60
999 999 0
0

Expected output

Example 3
Input
```
2
200 200
0 20
100 0
0
```
Expected output
```
2
```