(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.

Public test cases

**Input**

2 0 0 0 0 0 5 5 0 2 3 2 0 0 0 0 0 5 5 0 1 1 2 0 100 100 0 0 100 100 0 1 1 3 0 100 10 100 0 20 10 20 0 0 2 2 2 0 2 2 2 0 1 1 1 3 0 100 10 100 0 20 10 20 0 0 2 2 2 0 2 2 2 0 1 2 2 3 0 100 10 100 0 20 10 20 0 0 2 2 2 0 2 2 2 0 4 1 1

**Output**

1 3 0 2 2 1

Information

- Author
- Alex Alvarez
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++