← 返回题目列表

Codeforces · 1841/F

F. Monocarp 和战略游戏

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

Monocarp 玩一款战略电脑游戏,他在其中开发一座城市。这座城市居住着四个不同种族的生物——人类、精灵、兽人和矮人。

城市中的每个居民都有一个幸福值,它是一个整数。这取决于城市中有多少不同种族的生物居住。具体来说,每个居民的幸福感默认为$$$0$$$;对于同一种族的每个其他生物,它会增加 $$$1$$$;对于敌对种族的每个生物,它会减少 $$$1$$$。人类对兽人有敌意(反之亦然),精灵对矮人有敌意(反之亦然)。

游戏开始时,Monocarp 的城市无人居住。在游戏过程中,$$$n$$$ 一群生物会来到他的城市,希望在那里定居。第$$$i$$$组由$$$a_i$$$人类、$$$b_i$$$兽人、$$$c_i$$$精灵和$$$d_i$$$矮人组成。每次,Monocarp 要么接受整群生物进入城市,要么拒绝整群生物。

游戏根据以下公式计算Monocarp的得分:$$$m + k$$$,其中$$$m$$$是城市中的居民数量,$$$k$$$是城市中所有生物的幸福值总和。

帮助 Monocarp 在游戏结束时获得尽可能多的积分!

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^{5}$$$) — 来到 Monocarp 城市的生物群体数量。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含四个整数 $$$a_i$$$、$$$b_i$$$、$$$c_i$$$ 和 $$$d_i$$$ ($$$0 \leq a_i, b_i, c_i, d_i \leq 10^{9}$$$) — 人类、兽人、精灵和矮人的数量(分别)在第 $$$i$$$ 组中。

输出

输出一个数字——游戏结束时 Monocarp 可以获得的最大分数。如果您的答案的绝对或相对误差不超过 $$$10^{-9}$$$,则视为正确。也就是说,如果您的答案是 $$$a$$$,陪审团的答案是 $$$b$$$,那么如果 $$$\frac{|a-b|}{\max(1,|b|)} \le 10^{-9}$$$,则该解决方案将被接受。

请注意,正确的答案始终是整数,但有时它不适合 $$$64$$$ 位整数类型,因此允许您将其打印为非整数。

示例

输入 #1

5
0 0 1 0
1 3 4 2
2 5 1 2
4 5 4 3
1 4 4 5

输出 #1

85

输入 #2

4
3 3 1 5
5 1 5 3
4 4 4 1
1 3 4 4

输出 #2

41

注意

在第一个示例中,最好的做法是接受所有组。

在第二个示例中,最佳行动方案是接受组 $$$2$$$ 和 $$$3$$$,并拒绝组 $$$1$$$ 和 $$$4$$$。