题目翻译

维也纳被称为“文化之都”，其中原因之一是这座城市拥有超过$100$家博物馆。因此，无论你在维也纳停留多久，想要参观所有博物馆都是非常困难（且昂贵）的。幸运的是，有一个特殊的夜晚叫做“博物馆长夜”，在这个夜晚，你只需一张门票就可以参观许多博物馆，时间从下午$6$点持续到次日凌晨$1$点（共$7$小时）。

然而，仍然无法参观所有的博物馆，主要有两个原因：首先，维也纳的一些博物馆不参与此活动，因为它们下午$5$点就关门了。其次，在$7$小时内没有足够的时间去参观每一个博物馆、看完所有展览（否则就是浪费时间），然后再去其他博物馆。

给定参与“博物馆长夜”活动的博物馆数量、参观每个博物馆所需的时间，以及从一个博物馆到另一个博物馆的交通时间，你需要找到最佳的参观路线，以在“博物馆长夜”期间参观尽可能多的博物馆。

输入

输入包含多个测试用例。每个测试用例的第一行是一个整数$N$，表示参与活动的博物馆数量（$1 ≤ N ≤ 20$）。每个博物馆有一个唯一的编号，从$1$到$N$。第二行包含$N$个整数，表示参观每个博物馆所需的时间（单位：分钟）。接下来的$N$行描述了从一个博物馆到其他博物馆的交通时间。第$i$行包含$N$个整数$M$$_k$（$1 ≤ k ≤ N$），表示从博物馆$i$到博物馆$k$的交通时间（单位：分钟）。可以假设第$i$行的第$i$个整数为$0$。输入以$N = 0$结束。

输出

对于每个测试用例，输出一行，表示在“博物馆长夜”期间可以参观的博物馆的最大数量。

示例输入

2
500 500
0 120
200 0
2
220 220
0 30
20 0
2
150 150
0 120
200 0
0

示例输出

0
1
2

提示

你必须尽可能多地参观不同的博物馆。

来源

South America 2004