样例下载

题目描述

一张有向完全简单图，含有 n 个点，n·(n-1) 条边。点的编号为 1 ~ n。

点 i 会在时刻 $s_i$ 瞬间出现一个金币，并瞬间消失。你负责收集金币。如果你在 $s_i$ 时刻位于点 i 处，你便可以瞬间收集到该金币。

从点 i 到达点 j，需要花费的时间为 $t_{i,j}$。

初始时刻（即 0 时刻），你在点 1 处。你可以随时出发，但你之后每到达一个点，就一定会在该点收集到金币再离开。

问：你最多能收集到多少个金币？

输入格式

第一行：一个整数 $n$

接下来是 n 个整数，可能分布在若干行，依次表示 $s_i$

接下来是 $n^2$ 个整数，分布在若干行。如果把这些整数按输入顺序排成 n 行 n 列，则第 i 行第 j 列的整数表示 $t_{i,j}$。数据保证 $t_{i,i}=0$。

输出格式

一个整数，表示答案

样例输入

3
10
7 3
0 1 4
3 0 2
1 4
0

样例输出

2

样例解释

初始时 0 时刻，你在 1 号点。你花费 1 时间到达 2 号点，等待 6 时间，到 7 时刻，此刻 2 号点出现金币被你收集到，再花费 3 时间到达 1 号点，恰好 10 时刻，此刻 1 号点出现金币被你收集到。共收集到 2 个金币。

数据规模

100% 的数据，$1 ≤ n ≤ 400$，$0 ≤ s_i ≤ 10^9$，$1 ≤ t_{i,j} ≤ 10^6$。