3015 - 赶集

每年，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$ 个正数 $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$ 个摊位。 $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$ \le10^9 $，$ 1\leti,j$ $\le$ $10^6$ 。

来源

奇遇编程

题目参数

时间限制	1 秒
内存限制	32 MB
提交次数	0
通过人数	0

统计

上一题下一题