Greedy competition P70441


Statement
 

pdf   zip

html

A certain competition consists of several matches. Every match has a winner that obtains one point, while the loser gets nothing. At the end of the competition, the player with the highest score wins. If there are several tied contestants at the top, they all win.

After some matches, a player called Ivan wants to know if he can still win. Write a program that, given the current score of all the players, and information about the remaining matches, tells if Ivan can win or not.

Input

Input contains several cases. Every case begins with the number n of players, Ivan included. Follow n numbers with the current score of each player. Follow n lines with n numbers each, where the j-th number of the i-th line represents the number of matches still to play between player i and j. Assume 2 ≤ n ≤ 50, that the matrix is symmetric with zeros in the diagonal, that every given number is between 0 and 106, and that Ivan is the first player.

Output

For every case, print if Ivan can still win.

Public test cases
  • Input

    4
    6 10 10 1
    0 0 0 5
    0 0 4 0
    0 4 0 0
    5 0 0 0
    
    4
    6 11 9 9
    0 5 0 0
    5 0 0 0
    0 0 0 4
    0 0 4 0
    
    3
    20 0 0
    0 10 10
    10 0 81
    10 81 0
    
    2
    0 1000000
    0 1000000
    1000000 0
    

    Output

    no
    yes
    no
    yes
    
  • Information
    Author
    Alex Alvarez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Dotzè Concurs de Programació de la UPC - Final
    Date
    2014-10-01