Apocalypse Now P50934

(The original statement in Catalan has some private jokes. This English version goes straight to the point of the problem.)

We have several AI strategies for a two-player game, and we want to test their practical performance by confronting them. Each IA has been written by a different programmer. Unfortunately, every pair of programmers has a direct animosity. Two programmers can play against each other if they have a direct or undirect animosity with sum smaller than ‍100. For instance, with the animosity matrix

the programmers 0 and 1 can play each other, because through 2 the sum of animosities is just ‍30.

Additionally, there is another problem. Every programmer can ask for a maximum number of games every day. This number depends on the programmer.

Please write a program to compute the minimum number of days to play all the required games among the programmers that are fond enough.

Input

Input consists of several cases. Every case begins with the number of players n, between ‍2 and 30. Follows an n × n matrix, symmetric and with zeroes at the diagonal, where at position (i, j) there is the animosity between i and j (a natural number not larger than 100). Follow another n × n matrix, also symmetric and with zeroes at the diagonal, where at position (i, j) there is the minimum number of games needed to test those two AIs against each other (a number not larger than 10000). Finally, we have n numbers between 1 and 10000, to indicate how many games the i-th programmer can ask for every day.

Output

For every case, print the minimum number of days so that all pairs of IAs of fond enough programmers are tested as needed. Take into account that, for a game to be played, only one of the two programmers has to ask for it.