Перспектива#1927

Перспектива

2 секунди

256 мегабайтів

Дуже легка

Новини! Відомий мільярдер придбав ще не розкриту команду НБА. Він планує вкласти величезні зусилля та кошти, щоб зробити цю команду найкращою. Його мета чітка: перше місце.

Як його радник, ви повинні визначити, чи можливо, щоб ваша команда завершила сезон першою у своєму дивізіоні.

Більш формально, регулярний сезон НБА організований так: всі команди грають кілька ігор, в кожній з яких одна команда перемагає, а інша програє. Команди згруповані в дивізіони, деякі ігри проходять між командами одного дивізіону, а деякі — між командами з різних дивізіонів.

Враховуючи поточний рахунок і загальну кількість залишкових ігор для кожної команди вашого дивізіону, а також кількість залишкових ігор між кожною парою команд у вашому дивізіоні, визначте, чи можливо, щоб ваша команда набрала принаймні стільки ж перемог, скільки будь-яка інша команда у вашому дивізіоні.

Вхідні дані

Перший рядок містить $N$ ( $2 \leq N \leq 20$ 2 \le N \le 20) — кількість команд у вашому дивізіоні. Вони пронумеровані від $1$ до $N$ , ваша команда має номер $1$ .

Другий рядок містить $N$ цілих чисел $w_{1}, w_{2}, \dots, w_{N}$ w_1, w_2, \ldots, w_N, де $w_{i}$ w_i — загальна кількість ігор, які $i$ -та команда виграла на даний момент.

Третій рядок містить $N$ цілих чисел $r_{1}, r_{2}, \dots, r_{N}$ r_1, r_2, \ldots, r_N, де $r_{i}$ r_i — загальна кількість залишкових ігор для $i$ -ї команди (включаючи ігри всередині дивізіону).

Наступні $N$ рядків містять по $N$ цілих чисел кожен. $j$ -те число в $i$ -му рядку містить $a_{ij}$ a_{ij} — кількість залишкових ігор між командами $i$ та $j$ . Завжди вірно, що $a_{ij} = a_{j i}$ a_{ij} = a_{ji} і $a_{ii} = 0$ a_{ii} = 0. Для всіх $i$ виконується $a_{i 1} + a_{i 2} + \dots + a_{i N} \leq r_{i}$ a_{i1} + a_{i2} + \ldots + a_{iN} \le r_i.

Всі числа у вхідних даних є невід'ємними і не перевищують $10000$ .

Вихідні дані

У єдиному рядку виведіть YES (без лапок), якщо можливо, щоб команда $1$ набрала принаймні стільки ж перемог, скільки будь-яка інша команда у своєму дивізіоні, і NO (без лапок) в іншому випадку.

Приклади

Приклад 1