CF662E.To Hack or not to Hack

Consider a regular Codeforces round consisting of three problems that uses dynamic scoring.

You are given an almost final scoreboard. For each participant (including yourself), the time of the accepted submission for each of the problems is given. Also, for each solution you already know whether you are able to hack it or not. The only changes in the scoreboard that will happen before the end of the round are your challenges.

What is the best place you may take at the end?

More formally, n people are participating (including yourself). For any problem, if it was solved by exactly k people at the end of the round, the maximum score for this problem is defined as:

1. If n < 2_k_ ≤ 2_n_, then the maximum possible score is 500;
2. If n < 4_k_ ≤ 2_n_, then the maximum possible score is 1000;
3. If n < 8_k_ ≤ 2_n_, then the maximum possible score is 1500;
4. If n < 16_k_ ≤ 2_n_, then the maximum possible score is 2000;
5. If n < 32_k_ ≤ 2_n_, then the maximum possible score is 2500;
6. If 32_k_ ≤ n, then the maximum possible score is 3000.

Let the maximum possible score for some problem be equal to s. Then a contestant who didn't manage to get it accepted (or his solution was hacked) earns 0 points for this problem. If he got the the solution accepted t minutes after the beginning of the round (and his solution wasn't hacked), he earns points for this problem.

The overall score of a participant is equal to the sum of points he earns for each problem plus 100 points for each successful hack (only you make hacks).

The resulting place you get is equal to one plus the number of participants who's overall score is strictly greater than yours.

考虑一场标准的 Codeforces 比赛，共包含三道题目，采用动态得分机制。

你获得了一份近乎最终的排行榜。对于每位参赛者（包括你自己），已给出其每道题首次通过提交的时间。此外，对于每一份已通过的解答，你已知自己是否能够成功对其进行 Hack（即：能否成功提出反例使其失败）。在比赛结束前，排行榜上唯一可能发生的变动仅来自于你发起的 Hack。

那么，你在比赛结束时所能取得的最佳名次是多少？

更形式化地描述如下：共有 $ n $ 人参赛（含你自己）。对任意一道题目，若在比赛结束时恰好有 $ k $ 人通过了该题，则该题的最高可能得分定义为：

1. 若 $ n < 2k \leq 2n $，则该题最高可能得分为 $ 500 $；
2. 若 $ n < 4k \leq 2n $，则该题最高可能得分为 $ 1000 $；
3. 若 $ n < 8k \leq 2n $，则该题最高可能得分为 $ 1500 $；
4. 若 $ n < 16k \leq 2n $，则该题最高可能得分为 $ 2000 $；
5. 若 $ n < 32k \leq 2n $，则该题最高可能得分为 $ 2500 $；
6. 若 $ 32k \leq n $，则该题最高可能得分为 $ 3000 $。

设某题的最高可能得分为 $ s $。则：

• 若某选手未能通过该题（或其解答被 Hack），则他在该题得分为 $ 0 $；
• 若他在比赛开始后 $ t $ 分钟通过该题（且其解答未被 Hack），则他在该题得分为 。

一名选手的总得分为其三道题得分之和，再加上 每成功 Hack 一次所得的 $ 100 $ 分（仅你可进行 Hack）。

你的最终名次等于 总得分严格高于你的选手人数加一。

The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — the number of participants. You are the participant number 1.

Each of the following n lines contains three integers a__i, b__i and c__i. Here a__i = 0 means that the participant number i didn't manage to accept first problem. If 1 ≤ a__i ≤ 120, then the participant number i got the first problem accepted a__i minutes after the start of the contest and you cannot hack this solution. Finally,  - 120 ≤ a__i ≤  - 1 means that the participant number i got the first problem accepted  - a__i minutes after the start of the contest and you can hack this solution. Similarly, b__i and c__i provide the information regarding second and third problems in the same format.

It's guaranteed that integers _a_1, _b_1 and _c_1 are non-negative.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 5000$）—— 参赛者人数。你是编号为 1 的参赛者。

接下来的 $n$ 行中，每行包含三个整数 $a_i$、$b_i$ 和 $c_i$。其中，若 $a_i = 0$，表示编号为 $i$ 的参赛者未能通过第一题；若 $1 \leq a_i \leq 120$，则表示编号为 $i$ 的参赛者在比赛开始后 $a_i$ 分钟通过了第一题，且你不能对该解法进行 Hack；若 $-120 \leq a_i \leq -1$，则表示编号为 $i$ 的参赛者在比赛开始后 $-a_i$ 分钟通过了第一题，且你可以对该解法进行 Hack。类似地，$b_i$ 和 $c_i$ 以相同格式分别描述第二题和第三题的情况。

保证 $a_1$、$b_1$ 和 $c_1$ 均为非负整数。

Print the only integer — the best place you can take at the end of the round.

输出唯一的整数——你在本轮结束时所能获得的最佳名次。

Consider the first sample. If you do not hack any solutions, you will win the contest (scoreboard to the left). However, if you hack the solution of the first problem of the third participant (the only one you can hack), the maximum score for the first problem will change and you will finish second (scoreboard to the right).

考虑第一个样例。如果你不 hack 任何人的解答，你将赢得比赛（左侧的排行榜）。然而，如果你 hack 第三位参赛者的第一题解答（这是你唯一能 hack 的解答），那么第一题的最高得分将会改变，你将获得第二名（右侧的排行榜）。