Problem Description

Every year, FJ likes to go to the county fair. There are $n$ booths at the fair, and each booth $i$ will give out an exquisite gift at a specific time $p_i$ on that day. FJ has heard about this and hopes to collect as many gifts as possible to share with his cows. To get the gift from booth $i$, FJ must make sure he is at booth $i$ exactly at time $p_i$.

To collect as many gifts as possible, FJ did a detailed investigation. From this investigation, FJ determined the time $t_{i,j}$ it takes to travel from booth $i$ to booth $j$. The layout of the fair is very unusual, which means that if FJ chooses to detour via other booths while traveling from $i$ to $j$, it might take less time than going directly from $i$ to $j$. However, the straightforward FJ never does this: if he wants to go from booth $i$ to booth $j$, he will definitely spend $t_{i,j}$ time to walk from $i$ to $j$. In addition, because the fairground is rugged, $t_{i,j}$ may be different from $t_{j,i}$.

FJ is at booth $1$ at time $0$. Please compute the maximum number of gifts he can collect.

Input Format

Line $1$: An integer $n$, the number of booths.

Lines $2$ to $n+1$: $n$ integers. The integer on line $i+1$ is $p_i$, the time when booth $i$ gives out its gift.

Lines $n+2$ to $n^2+n+1$: $n^2$ lines. The first $n$ lines describe the time needed for FJ to walk from booth $1$ to booths $1$ to $n$ ($t_{1,1}, t_{1,2}, \ldots, t_{1,n}$). The next $n$ lines describe the time needed for FJ to walk from booth $2$ to booths $1$ to $n$ ($t_{2,1}, t_{2,2}, \ldots, t_{2,n}$), and so on. The last $n$ lines describe the time needed for FJ to walk from booth $n$ to booths $1$ to $n$ ($t_{n,1}, t_{n,2}, \ldots, t_{n,n}$). For any booth $i$, $t_{i,i}=0$.

Output Format

One line: An integer, the maximum number of gifts FJ can collect.

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

3

Hint

Sample Explanation

In the sample, there are $4$ booths at the fair. Booth $1$ gives out gifts at time $13$, booth $2$ at time $9$, booth $3$ at time $19$, and booth $4$ at time $3$.

FJ first walks from booth $1$ to booth $4$, which takes $3$ time units, and arrives at time $3$, so he can get the gift. Then he walks from booth $4$ to booth $2$, which takes $5$ time units, and arrives at time $8$. After waiting for $1$ time unit, he can get the gift from booth $2$. Next he walks from booth $2$ to booth $1$, which takes $4$ time units, and arrives at time $13$, so he can collect the third gift.

Constraints

For $100\%$ of the testdata, $1\le n\le 400$, $0\le p_i\le 10^9$, $1\le t_{i,j}\le 10^6$.

The testdata is from darkbzoj.

Translated by ChatGPT 5