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