Breaking news! A Russian billionaire has bought a yet undisclosed NBA team. He's planning to invest huge effort and money into making that team the best. And in fact he's been very specific about the expected result: the first place.

Being his adviser, you need to determine whether it's possible for your team to finish first in its division or not.

More formally, the NBA regular season is organized as follows: all teams play some games, in each game one team wins and one team loses. Teams are grouped into divisions, some games are between the teams in the same division, and some are between the teams in different divisions.

Given the current score and the total number of remaining games for each team of your division, and the number of remaining games between each pair of teams in your division, determine if it's possible for your team to score at least as much wins as any other team in your division.

Input

The first line contains n (2 ≤ n ≤ 20) - the number of teams in your division. They are numbered from 1 to n, your team has number 1.

The second line contains n integers w1, w2, ..., wn, where wi is the total number of games that i-th team has won to the moment.

The third line contains n integers r1, r2, ... rn, where ri is the total number of remaining games for the i-th team (including the games inside the division).

The next n lines contain n integers each. The j-th integer in the i-th line of those contains aij - the number of games remaining between teams i and j. It is always true that aij = aji and aii = 0, for all i the sum sum_jaij ≤ ri.

All the numbers in the input are non-negative and don't exceed 10000.

Output

Print YES if it's possible for the team 1 to score at least as much wins as any other team of its division, and NO otherwise.