Apocalypse Now P50934


Statement
 

pdf   zip

thehtml

(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




010010 
100020 
10200 



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++