题目描述

每年，FJ 都喜欢去参加县集市，集市上有 $n$ 个展位，每个摊位 $i$ 都会在当天的特定时间 $p_i$ 发放精美的礼品。FJ 已经听说了这一点，他希望能收集尽可能多的礼品和他的奶牛们一起分享。要想获得摊位 $i$ 发放的礼品，FJ 必须确保时间点 $p_i$ 时位于摊位 $i$。

为了获得尽可能多的礼品，FJ 进行了一番详细的调查，通过调查FJ确定了从摊位 $i$ 到摊位 $j$ 所花费的时间 $t_{i,j}$。集市的布局很不寻常，这会导致，FJ如果在从 $i$ 到 $j$ 的过程中选择从其他摊位绕行，可能会比直接从 $i$ 到 $j$ 所花费的时间更少，然而我们耿直的 FJ 从来不这么做，如果他想从摊位 $i$ 到摊位 $j$，他一定会花 $t_{i,j}$ 的时间从 $i$ 走到 $j$。另外由于集市所在地崎岖不平，所以 $t_{i,j}$ 可能与 $t_{j,i}$ 不相同。

FJ 在时间 $0$ 时，位于 $1$ 号摊位，请计算他最多可以收集多少奖品。

输入格式

第 $1$ 行：一个整数 $n$，表示摊位的数量。

第 $2$ 行：共 $n$ 个整数，其中第 $i+1$ 的正数 $p_i$ 表示摊位 $i$ 发放礼品的时间。

第 $n+2$ 到第 $n^2+n+1$ 行：共 $n^2$ 行，第一个 $n$ 行描述了 FJ 从摊位 $1$ 走到到摊位 $1$...$n$ 所需时间（$t_{1,1},t_{1,2}, ...t_{1,n}$），接下来的 $n$ 行描述了 FJ 从摊位 $2$ 走到摊位 $1$...$n$ 所需时间（$t_{2,1},t_{2,2}, ...t_{2,n}$），以此类推，最后的 $n$ 行描述了 FJ 从摊位 $n$ 走到摊位 $1$...$n$ 所需要的时间 $t_{n,1},t_{n,2}, ...t_{n,n}$。对于任意摊位 $i$，$t_{i,i}=0$。

输出格式

一行：一个整数，表示 FJ 最多可以领取到的奖品数量。

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

3

提示

样例说明

样例中集市上共有 $4$ 个摊位。$1$ 号摊位在时间 $13$ 发放礼品，$2$ 号摊位在时间 $9$ 发放礼品，$3$ 号摊位在时间 $19$ 发放礼品，$4$ 号摊位在时间 $3$ 发放礼品。

FJ 首先从 $1$ 号摊位走到 $4$ 号摊位，用时 $3$，并在时间 $3$ 到达，正好可以领取到奖品，接着他从摊位 $4$ 走到摊位 $2$ ，用时 $5$，并在时间 $8$ 到达，在等待 $1$ 个时间点后可以领取 $2$ 号摊位的礼品，接着他从 $2$ 号摊位走到 $1$ 号摊位，用时 $4$，并在时间 $13$ 到达，从而可以收集到第 $3$ 个礼品。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 400$，$0\le p_i\le 10^9$，$1\le t_{i,j}\le 10^6$。

数据来自 darkbzoj。