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$$$。