Thomas the Train
Description
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!
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}$.
Line $1$: An integer representing the maximum number of passengers Thomas can pick up.
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.
3
4
6
3
0 3 2
2 0 3
1 5 0
2
Note
$1 <= N <= 500$
$0 <= T_i <= 10^6$
$1 <= D_{i,j} <= 10^6$ for $i≠j$
$D_{i,i}$ = 0