| VK Cup 2017 - Раунд 3 |
|---|
| Закончено |
Вася и Петя участвуют в раунде Codeforces. Раунд длится два часа и состоит из пяти задач.
В раунде используется динамическая стоимость задач. Если вам посчастливилось ни разу не участвовать в раундах Codeforces с динамической стоимостью задач, поясним, что это значит. Максимальная стоимость задачи зависит от отношения числа решивших данную задачу к общему числу участников раунда, причем участниками раунда считаются все сделавшие хотя бы одну попытку.
Обратите внимание на границы диапазонов. Например, если в раунде участвуют 40 человек, а задачу решили 10 из них, то доля решивших равна 1 / 4, а максимальная стоимость задачи равна 1500.
Если максимальная стоимость задачи равна x, то за каждую целую минуту, прошедшую от начала раунда до отправки участником верного решения по задаче, участник потеряет x / 250 баллов. Например, если максимальная стоимость задачи равна 2000, а участник отправил верное решение по ней спустя 40 минут после начала раунда, то этому участнику будет начислено 2000·(1 - 40 / 250) = 1680 баллов за эту задачу.
Всего в раунде n участников, считая Васю и Петю. Про каждого участника и каждую задачу известно, сколько целых минут прошло от начала раунда до отправки данным участником решения по данной задаче, или что участник не делал попыток по задаче.
За две секунды до конца раунда оказалось так, что все попытки участников прошли претесты, а также не было сделано ни одной попытки взлома. Вася полагает, что за оставшиеся две секунды никто не успеет отправить решение или попытаться взломать другое решение, а все уже сделанные попытки участников успешно пройдут системное тестирование.
К сожалению, Вася — обманщик и еще до начала раунда зарегистрировал на него 109 + 7 новых аккаунтов. Теперь Вася может отправить от имени новых аккаунтов любые из своих решений, чтобы изменить окончательные стоимости задач. Кроме того, Вася может отправлять неправильные решения на любые задачи. Обратите внимание, что Вася не может отправлять правильные решения на те задачи, которые он сам не решил.
Вася стремится к тому, чтобы набрать на текущем раунде строго больше баллов, чем Петя. Скрипты, позволяющие обфусцировать решения Васи и отправлять их в систему от имени любого из новых аккаунтов за доли секунды, у Васи уже готовы. Однако Вася не хочет делать свой обман слишком очевидным, поэтому он желает достичь своей цели, сделав попытки от имени как можно меньшего числа новых аккаунтов.
Найдите минимальное число новых аккаунтов, необходимое Васе для того, чтобы обогнать Петю (при условии, что предположения Васи верны), или сообщите, что Вася не сможет достичь своей цели.
Первая строка содержит целое число n (2 ≤ n ≤ 120) — количество участников раунда, считая Васю и Петю.
Каждая из следующих n строк содержит пять целых чисел ai, 1, ai, 2..., ai, 5 ( - 1 ≤ ai, j ≤ 119) — количество целых минут, прошедших от начала раунда до отправки участником i решения по задаче j, либо -1, если участник i не делал попыток по задаче j.
Гарантируется, что каждый участник сделал хотя бы одну попытку.
Вася — участник под номером 1, Петя — участник под номером 2, остальные участники даны в произвольном порядке.
Выведите единственное число — минимальное число новых аккаунтов, необходимое Васе для того, чтобы обогнать Петю, или - 1, если Вася не сможет достичь своей цели.
2
5 15 40 70 115
50 45 40 30 15
2
3
55 80 10 -1 -1
15 -1 79 60 -1
42 -1 13 -1 -1
3
5
119 119 119 119 119
0 0 0 0 -1
20 65 12 73 77
78 112 22 23 11
1 78 60 111 62
27
4
-1 20 40 77 119
30 10 73 50 107
21 29 -1 64 98
117 65 -1 -1 -1
-1
В первом примере оптимальная стратегия Васи — отправить от имени двух новых аккаунтов решения последних трех задач. В таком случае первые две задачи будут иметь стоимость 1000, а последние три — 500. Общее число баллов Васи составит 980 + 940 + 420 + 360 + 270 = 2970, а Петя наберет лишь 800 + 820 + 420 + 440 + 470 = 2950 баллов.
Во втором примере Васе следует от имени двух новых аккаунтов отправить по одному неверному решению на любую из задач, а от имени еще одного нового аккаунта — отправить только верное решение по первой задаче. В этом случае максимальные стоимости задач составят 500, 1500, 1000, 1500, 3000. Вася наберет 2370 баллов, а Петя — 2294 балла.
В третьем примере Вася добьется желаемого, если отправит решения первых четырех задач от имени 27 новых аккаунтов. Тогда стоимости задач составят 500, 500, 500, 500, 2000. Благодаря высокой стоимости пятой задачи Вася сможет обойти Петю, очень быстро решившего первые четыре задачи, но не решившего пятую.
