The County Fair

Every year, Farmer Ran (FR) loves to attend the county fair. The fair
has N booths (1 <= N <= 400), and each booth i is planning to give
away a fabulous prize at a particular time P(i) (0 <= P(i) <=
1,000,000,000) during the day. He has heard about this and
would like to collect as many fabulous prizes as possible to share
with his aliens. He would like to show up at a maximum possible number
of booths at the exact times the prizes are going to be awarded.

FR investigated and has determined the time T(i,j) (always in range
1..1,000,000) that it takes him to walk from booth i to booth j.
The county fair's unusual layout means that perhaps FR could travel
from booth i to booth j by a faster route if he were to visit
intermediate booths along the way. Being a poor map reader, Farmer
Ran never considers taking such routes -- he will only walk from
booth i to booth j in the event that he can actually collect a
fabulous prize at booth j, and he never visits intermediate booths
along the way. Furthermore, T(i,j) might not have the same value
as T(j,i) owing to FR's slow walking up hills.

Farmer Ran starts at booth #1 at time 0. Help him collect as many
fabulous prizes as possible.

CODE NAME: fair.X

INPUT FORMAT:

* Line 1: A single integer: N.

* Lines 2..1+N: Line i+1 contains a single integer: P(i).

* Lines 2+N..1+N+N^2: These N^2 lines each contain a single integer
        T(i,j) for each pair (i,j) of booths. The first N of these
        lines respectively contain T(1,1), T(1,2), ..., T(1,N). The
        next N lines contain T(2,1), T(2,2), ..., T(2,N), and so on.
        Each T(i,j) value is in the range 1...1,000,000 except for the
        diagonals T(1,1), T(2,2), ..., T(N,N), which have the value
        zero.

SAMPLE INPUT:

4
13
9
19
3
0
10
20
3
4
0
11
2
1
15
0
12
5
5
13
0

INPUT DETAILS:

There are 4 booths. Booth #1 is giving away a prize at time 13, booth #2
at time 9, booth #3 at time 19, and booth #4 at time 3.

OUTPUT FORMAT:

* Line 1: A single integer, containing the maximum number of prizes
        Farmer Ran can acquire.

SAMPLE OUTPUT (file cfair.out):

3

OUTPUT DETAILS:

Farmer Ran first walks to booth #4 and arrives at time 3, just in
time to receive the fabulous prize there. He them walks to booth
#2 (always walking directly, never using intermediate booths!) and
arrives at time 8, so after waiting 1 unit of time he receives the
fabulous prize there. Finally, he walks back to booth #1, arrives
at time 13, and collects his third fabulous prize.