카운티 축제

Farmer John은 해마다 카운티 축제에 간다. 축제장에는 부스가 $N$개 있고, 부스 $i$는 그날 정확히 시각 $P(i)$에 경품을 하나 준다. John은 소들과 나눌 경품을 최대한 많이 모으려고, 경품이 나오는 바로 그 시각에 되도록 많은 부스에 서 있으려 한다.

부스 $i$에서 부스 $j$로 곧장 걸어가는 데는 $T(i,j)$만큼 걸린다. 축제장 배치가 특이해서 다른 부스를 거치면 더 빠른 경로가 있기도 하지만, John은 지도를 잘 읽지 못해 그런 경로를 전혀 떠올리지 못한다. 부스 $j$에서 실제로 경품을 받을 수 있을 때만 부스 $i$에서 부스 $j$로 걸어가며, 가는 길에 다른 부스를 들르지 않는다. 오르막에서는 걸음이 느려지므로 $T(i,j)$와 $T(j,i)$가 다를 수 있다.

John은 시각 0에 부스 1에 있다. 이동 규칙은 다음과 같다.

• 어떤 부스에서 경품을 받으면 그 즉시 떠난다. 즉 부스 $i$를 떠나는 시각은 $P(i)$다. 출발할 때만 예외로, 부스 1의 경품을 받지 않고 시각 0에 떠날 수 있다.
• 반대로 처음부터 부스 1에 머물러 시각 $P(1)$에 경품을 받아도 된다.
• 시각 $t$에 부스 $i$를 떠나면 부스 $j$에 시각 $t + T(i,j)$에 닿는다. $t + T(i,j) \le P(j)$인 부스 $j$로만 걸어가고, 도착한 뒤에는 시각 $P(j)$까지 기다렸다가 경품을 받는다.
• 부스마다 경품은 한 번만 나오므로 같은 부스를 두 번 세지 않는다.

John이 받을 수 있는 경품의 최대 개수를 구하시오.

첫째 줄에 $N$이 주어진다. ($1 \le N \le 400$)

다음 $N$개 줄의 $i$번째 줄에 부스 $i$가 경품을 주는 시각 $P(i)$가 주어진다. ($0 \le P(i) \le 10^9$)

그다음 $N^2$개 줄에는 순서쌍 $(i, j)$마다 $T(i,j)$가 한 줄에 하나씩 주어진다. 처음 $N$개 줄은 차례로 $T(1,1), T(1,2), \dots, T(1,N)$이고, 다음 $N$개 줄은 $T(2,1), T(2,2), \dots, T(2,N)$이며, 이런 식으로 이어진다. 대각선 성분 $T(1,1), T(2,2), \dots, T(N,N)$은 0이고, 나머지 성분은 $1 \le T(i,j) \le 10^6$을 만족한다.

첫째 줄에 John이 받을 수 있는 경품의 최대 개수를 출력한다.