分数: 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