Greedy competition P70441

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 10⁶, and that Ivan is the first player.

Output

For every case, print if Ivan can still win.