Перспектива
Новини! Російський мільярдер придбав ще не розкриту команду НБА. Він планує вкласти величезні зусилля та кошти, щоб зробити цю команду найкращою. Його мета чітка: перше місце.
Як його радник, ви повинні визначити, чи можливо, щоб ваша команда завершила сезон першою у своєму дивізіоні.
Більш формально, регулярний сезон НБА організований так: всі команди грають кілька ігор, в кожній з яких одна команда перемагає, а інша програє. Команди згруповані в дивізіони, деякі ігри проходять між командами одного дивізіону, а деякі — між командами з різних дивізіонів.
Враховуючи поточний рахунок і загальну кількість залишкових ігор для кожної команди вашого дивізіону, а також кількість залишкових ігор між кожною парою команд у вашому дивізіоні, визначте, чи можливо, щоб ваша команда набрала принаймні стільки ж перемог, скільки будь-яка інша команда у вашому дивізіоні.
Вхідні дані
Перша строка вхідних даних містить N (2 ≤ N ≤ 20) — кількість команд у вашому дивізіоні. Вони пронумеровані від 1 до N, ваша команда має номер 1.
Друга строка вхідних даних містить N цілих чисел w_1, w_2,..., w_N, де w_i — загальна кількість ігор, які i-та команда виграла на даний момент.
Третя строка вхідних даних містить N цілих чисел r_1, r_2,..., r_N, де r_i — загальна кількість залишкових ігор для i-ї команди (включаючи ігри всередині дивізіону).
Наступні N рядків містять по N цілих чисел кожен. j-те число в i-му рядку містить a_ij — кількість залишкових ігор між командами i та j. Завжди вірно, що a_ij=a_ji і a_ii=0, для всіх i a_i1 + a_i2 +... + a_iN ≤ r_i.
Всі числа у вхідних даних є невід'ємними і не перевищують 10,000.
Вихідні дані
На єдиній строкі вихідних даних виведіть "YES" (без лапок), якщо можливо, щоб команда 1 набрала принаймні стільки ж перемог, скільки будь-яка інша команда у своєму дивізіоні, і "NO" (без лапок) в іншому випадку.