← 返回题目列表

Codeforces · 773/B

B. 动态问题评分

中文机器翻译题面 查看原题

Vasya 和 Petya 参加 Codeforces 回合。该轮持续两个小时,包含五个问题。

本轮使用动态问题评分。如果您很幸运没有参加任何具有动态问题评分的 Codeforces 回合,那么这意味着什么。问题的最大分值取决于解决该问题的参与者人数占回合参与者总数的比例。每个至少提交一份作品的人都被视为参加这一轮。

$$\begin{数组}{|c|c|}
\hline
\text{求解器分数} & \text{最大点值} \\
\hline
(1/2, 1] & 500 \\
(1/4, 1/2] & 1000 \\
(1/8, 1/4] & 1500 \\
(1/16, 1/8] & 2000 \\
(1/32, 1/16] & 2500 \\
[0, 1/32] & 3000 \\
\hline
\end{数组}$$

注意范围界限。例如,如果有 40 人参加该轮比赛,其中 10 人解决了特定问题,则解决者分数等于 1 / 4,并且问题的最大分值等于 1500。

如果问题的最大分值等于x,则从比赛开始到参赛者正确提交的每一整分钟,参赛者都会损失x / 250分。例如,如果问题的最高分值为2000,并且参与者在该轮开始后40分钟提交了正确的解决方案,则该参与者将获得该问题的2000·(1 - 40 / 250) = 1680分。

本轮有 n 名参赛者,包括 Vasya 和 Petya。对于每个参与者和每个问题,从比赛开始到该参与者提交该问题之间经过的分钟数是已知的。该参与者也可能没有对此问题提交任何意见。

距离本轮结束还有两秒,所有参与者提交的内容都已通过预测试,并且没有发生任何黑客尝试。 Vasya相信,在剩下的两秒内,不会再有任何提交或黑客尝试,每一次提交都会通过系统测试。

不幸的是,Vasya 是个骗子。他本轮注册了 109 + 7 个新账户。现在,Vasya 可以从这些新帐户提交他的任何解决方案,以更改问题的最大分值。 Vasya 还可以针对任何问题提交任何错误的解决方案。请注意,Vasya 无法针对他未解决的问题提交正确的解决方案。

Vasya 希望在本轮比赛中获得比 Petya 更多的分数。 Vasya 已经准备好了脚本,可以混淆他的解决方案,并在几分之一秒内将它们从任何新帐户提交到系统中。然而,Vasya 不想让自己的作弊行为太过明显,因此他希望通过尽可能少的新帐户提交内容来实现自己的目标。

找到 Vasya 击败 Petya 所需的最少新帐户数量(假设 Vasya 的假设正确),或者报告 Vasya 无法实现他的目标。

输入

第一行包含一个整数 n (2 ≤ n ≤ 120) — 回合参与者的数量,包括 Vasya 和 Petya。

接下来的 n 行中的每一行都包含五个整数 ai, 1, ai, 2..., ai, 5 (- 1 ≤ ai, j ≤ 119) - 回合开始和参与者 i 提交问题 j 之间经过的分钟数,如果参与者 i 尚未解决问题 j,则为 -1。

保证每位参赛者至少成功提交一次。

Vasya 被列为 1 号参与者,Petya 被列为 2 号参与者,所有其他参与者排名不分先后。

输出

输出一个整数 - Vasya 需要击败 Petya 的新帐户数量,如果 Vasya 无法实现他的目标,则输出 -1。

示例

输入 #1

2
5 15 40 70 115
50 45 40 30 15

输出 #1

2

输入 #2

3
55 80 10 -1 -1
15 -1 79 60 -1
42 -1 13 -1 -1

输出 #2

3

输入 #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

输出 #3

27

输入#4

4
-1 20 40 77 119
30 10 73 50 107
21 29 -1 64 98
117 65 -1 -1 -1

输出#4

-1

注意

在第一个示例中,Vasya 的最佳策略是从两个新帐户提交最后三个问题的解决方案。在这种情况下,前两题的最高分值为 1000,而后三题的最高分值为 500。Vasya 的得分将等于 980 + 940 + 420 + 360 + 270 = 2970 分,而 Petya 的得分仅为 800 + 820 + 420 + 440 + 470 = 2950 分。

在第二个示例中,Vasya 必须从两个新帐户对任何问题进行一次不成功的提交,并从第三个新帐户对第一个问题进行一次成功提交。在这种情况下,问题的最大分值将等于 500、1500、1000、1500、3000。Vasya 的得分为 2370 分,而 Petya 的得分仅为 2294 分。

在第三个示例中,Vasya 可以通过提交 27 个新帐户的前四个问题的解决方案来实现他的目标。这些问题的最高分值将等于 500, 500, 500, 500, 2000。由于第五个问题的高成本,Vasya 将设法击败 Petya,Petya 很快解决了前四个问题,但无法解决第五个问题。