题目描述

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

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

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

输入格式

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

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

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

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

输出格式

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

样例

输入样例

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

输出样例

3

提示

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

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

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

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

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

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

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

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