Рассмотрим раунд Codeforces, состоящий из трёх задач и использующий динамическую разбалловку.
Дана почти финальная таблица. Для каждого участника (включая вас) известно время, когда он сдал каждую из задач (или не сдал вовсе). Также про каждое из решений известно, можете вы его взломать или нет. Считаем, что единственные изменения до конца раунда — это ваши взломы.
Какое наивысшее место вы можете занимать в конце раунда?
Более формально: в раунде участвуют n человек, включая вас. Если некоторую задачу в конце раунда (после ваших взломов) решило k человек, то максимальный балл за эту задачу определяется следующим образом:
- Если n < 2k ≤ 2n, то максимальный балл — 500;
- Если n < 4k ≤ 2n, то максимальный балл — 1000;
- Если n < 8k ≤ 2n, то максимальный балл — 1500;
- Если n < 16k ≤ 2n, то максимальный балл — 2000;
- Если n < 32k ≤ 2n, то максимальный балл — 2500;
- Если 32k ≤ n, то максимальный балл — 3000.
Пусть максимальный балл за некоторую задачу равен s, тогда если человек не решил эту задачу (или вы взломали его решение), то он получает 0 баллов за эту задачу. Если человек решил данную задачу через t минут после начала раунда (и его решение не было взломано), то его балл за эту задачу равен 
.
Суммарный балл участника равен сумме его баллов по всем трём задачам плюс по 100 баллов за каждый успешный взлом (взломы делаете только вы).
Ваше место в конце раунда будет определяться как один плюс количество участников, суммарный балл которых строго больше вашего суммарного балла.
В первой строке входных данных задано число n (1 ≤ n ≤ 5000) — количество участников. Вы являетесь участником под номером 1.
Следующие n строк содержат по три целых числа ai, bi и ci. Здесь ai = 0 означает, что участник под номером i не решил первую задачу. 1 ≤ ai ≤ 120 означает, что участник под номером i решил первую задачу через ai минут после начала контеста, и вы не можете взломать его решение. - 120 ≤ ai ≤ - 1 означает, что участник под номером i решил первую задачу через - ai минут после начала контеста и вы можете взломать его решение. bi и ci описывают вторую и третью задачи в аналогичном формате.
Гарантируется, что все три числа a1, b1 и c1 неотрицательны.
Выведите одно число — самое высокое место, которые Вы можете занять, взломав некоторые решения.
4
120 120 1
61 61 120
-61 61 120
0 0 0
1
4
0 0 119
-3 -17 -42
0 7 0
51 0 0
2
Рассмотрим первый пример. Если не взламывать ни одно решение, то вы займете первое место (таблица слева). Если же взломать решение третьего участника по первой задаче (единственное, которое вы можете взломать), то максимальный балл за первую задачу изменится, и вы займете второе место (таблица справа).
