Perspective — Eolymp

Input

The first line contains $N$ ( $2 \leq N \leq 20$ 2 \le N \le 20) — the number of teams in your division. They are numbered from $1$ to $N$ , your team is number $1$ .

The second line contains $N$ integers $w_{1}, w_{2}, \dots, w_{N}$ w_1, w_2, \ldots, w_N, where $w_{i}$ w_i is the total number of games the $i$ -th team has won so far.

The third line contains $N$ integers $r_{1}, r_{2}, \dots, r_{N}$ r_1, r_2, \ldots, r_N, where $r_{i}$ r_i is the total number of remaining games for the $i$ -th team (including games inside the division).

The next $N$ lines contain $N$ integers each. The $j$ -th number in the $i$ -th line, $a_{ij}$ a_{ij}, is the number of games remaining between teams $i$ and $j$ . It is always true that $a_{ij} = a_{j i}$ a_{ij} = a_{ji} and $a_{ii} = 0$ a_{ii} = 0. For all $i$ it holds that $a_{i 1} + a_{i 2} + \dots + a_{i N} \leq r_{i}$ a_{i1} + a_{i2} + \ldots + a_{iN} \le r_i.

All numbers in input are non-negative and do not exceed $10000$ .

Output

Print **YES** (without quotes) if it is possible for team $1$ to have at least as many wins as any other team in its division, and **NO** (without quotes) otherwise.

Examples

Example 1

Loading