题目描述

每一年，约翰都会带着他的奶牛们去赶集．集会中一共有${N(1≤}$${N≤}$${400)}$个商店，第${i}$个商店会在特定的时间${P_i(0≤}$${P_i≤}$${10^9)}$对当时在店里的顾客送出一份精美的礼物．约翰当然得到了这个消息，于是他希望能拿到尽量多的礼物送给他的奶牛们．也就是说，他想尽可能多地在某商店发放礼物的时候，正好呆在店里．

经过一定的调查，约翰弄清楚了从${i}$号商店走到${J}$号商店所需要的时间${T_i，}$${J(1≤}$${T_i，}$${J≤}$${1000000)}$．虽然乡间小路 奇特的布局使得从${i}$号商店走到${j}$号商店的最短路不一定是直接连接这两个商店的那条，但约翰并不会选择那些会经过其他商店的路线，只是直接走到目标商店等 待礼物的送出．此外，${T_i,j}$并不一定等于${Tj,i，}$由于约翰爬山的速度总是很慢．

约翰在时间${0}$时于${1}$号商店开始他的旅途．请你帮他设计一条路线来获得尽可能多的礼物．

输入格式

第${1}$行输入一个正整数${N}$．

接下来${N}$行每行一个整数${P_i}$．

接下来${N^2}$行，输入乃，${J}$．

先输入${T1,1 T1,2 T1,3}$…${T1,N}$再输入${T2,1 T2,2}$…${T2,N}$依次类推．

输出格式

输出一个整数，即约翰最多能拿到的礼物的个数

样例

输入样例

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

输出样例

3

提示

${//}$有四个收藏品可以去收集,下面四行给出这四个东西下落的时间

${//}$第一个东西，在第一个地点第${13}$分钟掉下来

${//}$第二个东西，在第二个地点第${9}$分钟掉下来

${//}$第三个东西，在第三个地点第${19}$分钟掉下来

${//}$这是第四个东西.

${//}$这下面有${4\times4}$行，代表每个点到其它点的要花的时间，自己到自己的时间为${0}$。

农民约翰首先走到${4}$号摊位，在${3}$点到达，正好在那里收到了精彩的奖品。他走到${2}$号摊位（总是直接走，从不使用中间摊位！）并且在时间${8}$到 达，所以在等待了${1}$个单位的时间后，他在那里收到了神话般的奖品。最后，他走回摊位#${1，}$在${13}$点到达，并收集他的第三个神话般的奖项。

一共有${4}$家商店．${1}$号商店会在时间${13}$送出一份礼物，${2}$号商店送出礼物的时间为${9，}$${3}$号商店是时间${19，}$${4}$ 号商店是时间${3}$． 约翰先在时间${3}$走到${4}$号商店，正好拿到送出的礼物．然后他再直接走到${2}$号商店（不经过任何中转商店），在时间${8}$到那儿，然后等待${1}$单位时间，在时间${9}$拿到商店送出的礼物后马上出发去${1}$号商店，又正好能在时间${13}$到达并拿到第${3}$份礼物．