题目描述

有两位魔法使 $X$ 和 $Y$ 正在与怪物战斗。

一开始，两人的魔力均为 $0$。他们都掌握以下两种魔法：

• 魔法 $1$：使用者的魔力增加 $1$。
• 魔法 $2$：对怪物造成等同于使用者当前魔力的伤害。

两人各自使用 $N$ 次魔法后撤退。
对于每一次 $i=1,\ldots,N$，两人可以选择以下两种魔法组合之一：

• $X$ 使用魔法 $a_i$，$Y$ 使用魔法 $b_i$。
• $X$ 使用魔法 $c_i$，$Y$ 使用魔法 $d_i$。

请你求出在两人撤退前，对怪物造成的总伤害的最大值。

输入格式

输入以如下格式从标准输入读入。

$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

输出

3

样例 2

输入

5
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 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

输出

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

输出

138

说明/提示

限制条件

• $1 \leq N \leq 8000$
• $a_i, b_i, c_i, d_i \in \{1,2\}$
• 输入均为整数

样例解释 1

按如下方式可以达到最大值：

• 第 $1$ 次魔法选择 $a_1=1,\, b_1=1$。$X$ 和 $Y$ 的魔力都变为 $1$。
• 第 $2$ 次魔法选择 $c_2=2,\, d_2=2$。总共对怪物造成 $2$ 点伤害。
• 第 $3$ 次魔法选择 $a_3=2,\, b_3=1$。$X$ 的魔法对怪物造成 $1$ 点伤害，$Y$ 的魔力变为 $2$。

样例解释 2

如果魔力为 $0$ 时使用魔法 $2$，则无法造成伤害。

由 ChatGPT 4.1 翻译