← 返回题目列表

AtCoder · arc142_f

F. 配对巫师

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

分数: 1000 点

问题陈述

两个巫师, X 和 Y,正在与怪物战斗。

最初,每个巫师的魔力为 0。他们知道以下两个咒语。

  • 法术 1:使施法者的魔法强度增加 1.
  • 法术 2:对怪物造成等同于施法者魔法强度的伤害。

每个巫师使用咒语后 N 次,他们将退出战斗。
对于每个 i=1, \ldots, N,他们必须使用以下法术组合之一 i第一个咒语。

  • X 施放法术 a_i,和 Y 施放法术 b_i.
  • X 施放法术 c_i,和 Y 施放法术 d_i.

找出在撤退前可以对怪物造成的最大总伤害。

约束

  • 1 \leq N \leq 8000
  • a_i,b_i,c_i,d_i \in \{1,2\}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
a_1 b_1 c_1 d_1
\vdots
a_N b_N c_N d_N

输出

打印答案。


示例输入 1

3
1 1 2 2
2 1 2 2
2 1 1 1

示例输出 1

3

可以达到的最大总伤害如下。

  • 作为 1-st 法术,使用 a_1=1,\, b_1=1,增加两者 X的和 Y的魔力 1.
  • 作为 2-nd 法术,使用 c_2=2,\, d_2=2,交易 总计 2 点伤害。
  • 作为 3-rd 法术,使用 a_3=2,\, b_3=1,交易 总计 1 点伤害 X的咒语和增加 Y的魔力 2.

示例输入 2

5
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2

示例输出 2

0

施法咒语 2 具有魔力 0 不造成伤害。


示例输入 3

8
1 1 2 2
2 2 2 1
1 1 2 1
1 1 2 2
2 1 1 1
1 2 1 2
2 1 1 2
2 1 2 1

示例输出 3

20

示例输入 4

20
2 1 2 1
2 1 1 1
1 2 1 1
2 2 1 2
2 2 2 1
1 1 2 1
1 2 2 2
2 2 2 1
1 1 1 2
1 2 1 2
1 2 2 2
2 1 1 2
2 1 1 1
1 2 1 2
1 2 1 2
1 1 1 2
1 1 2 1
2 2 1 1
1 2 2 2
2 1 1 2

示例输出 4

138