Maximizing Gift Collection at the Fair

Every year, Farmer John (FJ) enjoys attending the county fair, which features \(n\) booths. Each booth \(i\) distributes a beautiful gift at an exact time \(p_i\). To obtain the gift from booth \(i\), FJ must be present at that booth exactly at time \(p_i\>.

FJ has also determined the travel time between booths. In particular, if he goes directly from booth \(i\) to booth \(j\), he will spend exactly \(t_{i,j}\) units of time. Note that \(t_{i,j}\) may not equal \(t_{j,i}\). Although it might sometimes be beneficial to detour, our honest FJ always travels directly between booths.

Initially, FJ is at booth 1 at time 0. He may choose either to wait at a booth if he arrives early or to depart immediately. Given the information, determine the maximum number of gifts FJ can collect.

inputFormat

The first line contains an integer \(n\), representing the number of booths. The second line contains \(n\) space-separated integers \(p_1, p_2, \dots, p_n\), where \(p_i\) is the time when booth \(i\) distributes its gift. This is followed by \(n\) lines, each containing \(n\) space-separated integers. The \(j\)th number on the \(i\)th line is \(t_{i,j}\), the time required to travel directly from booth \(i\) to booth \(j\).

outputFormat

Output a single integer — the maximum number of gifts FJ can collect.

sample

3
0 5 10
0 3 10
5 0 5
10 5 0

3