Последние новости! Российский миллиардер купил еще нераскрытую команду НБА. Он планирует вкладывать огромные усилия и деньги в то, чтобы сделать эту команду лучшей. И на самом деле он очень точно оценил ожидаемый результат: первое место.

Будучи его советником, Вам нужно определить, сможет ли Ваша команда стать первой в своем дивизионе или нет.

Более формально, регулярный сезон НБА организован следующим образом: все команды играют несколько игр, в каждой игре выигрывает одна команда, а другая проигрывает. Команды группируются в дивизионы, некоторые игры проводятся между командами одного дивизиона, а некоторые - между командами разных дивизионов.

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

Входные данные

Первая строка содержит число n (2 ≤ n ≤ 20) - количество команд в Вашем дивизионе. Они пронумерованы от 1 до n, Ваша команда имеет номер 1.

Вторая строка содержит n целых чисел w1, w2, ..., wn, где wi - общее количество игр которое i-ая команда выиграла к данному моменту.

Третья строка содержит n целых чисел r1, r2, ... rn, где ri - общее количество оставшихся игр для i-ой команды (включая игры внутри дивизиона).

Каждая мз следующих n строк содержит n целых чисел. j-ое число в i-ой строке содержит aij - количество игр, которое осталось сыграть командам i и j. Известно, что aij = aji и aii = 0, для всех i сумма sum_jaij ≤ ri.

Все входные числа неотрицательны и не превосходят 10000.

Выходные данные

Выведите YES, если команда 1 сможет выиграть как минимум столько же раз, сколько это сделает любая другая команда в дивизионе, и NO иначе.