I. Thomas the Train
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Thomas the Train, an artificial intelligence technology, is traveling between his $$$N$$$ train stations labeled $$$1$$$ to $$$N$$$, and he starts at station $$$1$$$. He knows that today, for each station $$$i$$$, one passenger will arrive at station $$$i$$$ at time $$$T_i$$$. It takes an amount of time $$$D_{i, j}$$$ to drive from station i to station j. Note that $$$D_{i, j}$$$ may differ from $$$D_{j, i}$$$.

Since Thomas is not very intelligent, Thomas travels to a station only if he will pick up a passenger there, and thus he does not take a shorter path to a station involving intermediate stations without picking up passengers there. Furthermore, the passengers are very impatient and unwilling to wait at a station for any amount of time, so Thomas must pick up passengers at the exact time at which they arrive. He can wait at a station for as long as he wants. Help Thomas determine the maximum number of passengers he can pick up today!

Input

Line $$$1$$$: An integer $$$N$$$.

Lines $$$2…N+1$$$: An integer $$$T_i$$$ denoting the time at which a passenger will arrive at station $$$i$$$.

Lines $$$N+2…2N+1$$$: A sequence of $$$N$$$ integers each denoting an amount of time $$$D_{i, j}$$$, starting with $$$D_{1, 1}$$$ through $$$D_{1, N}$$$ and ending with $$$D_{N, 1}$$$ through $$$D_{N, N}$$$.

Output

Line $$$1$$$: An integer representing the maximum number of passengers Thomas can pick up.

Example
Input
3
4
6
3
0 3 2
2 0 3
1 5 0
Output
2
Note

$$$1 \lt = N \lt = 500$$$

$$$0 \lt = T_i \lt = 10^6$$$

$$$1 \lt = D_{i,j} \lt = 10^6$$$ for $$$i≠j$$$

$$$D_{i,i}$$$ = 0