Перспектива
Последние новости! Российский миллиардер купил еще нераскрытую команду НБА. Он планирует вкладывать огромные усилия и деньги в то, чтобы сделать эту команду лучшей. И на самом деле он очень точно оценил ожидаемый результат: первое место.
Будучи его советником, Вам нужно определить, сможет ли Ваша команда стать первой в своем дивизионе или нет.
Более формально, регулярный сезон НБА организован следующим образом: все команды играют несколько игр, в каждой игре выигрывает одна команда, а другая проигрывает. Команды группируются в дивизионы, некоторые игры проводятся между командами одного дивизиона, а некоторые - между командами разных дивизионов.
Учитывая текущий счет и общее количество оставшихся игр для каждой команды Вашего дивизиона и количество оставшихся игр между каждой парой команд в дивизионе, определите, сможет ли Ваша команда набрать как минимум столько же побед, сколько и другие команды Вашего дивизиона.
Входные данные
Первая строка содержит число 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 сумма sum_j a[ij] ≤ r[i].
Все входные числа неотрицательны и не превосходят 10000.
Выходные данные
Выведите YES, если команда 1 сможет выиграть как минимум столько же раз, сколько это сделает любая другая команда в дивизионе, и NO иначе.