题目描述

两个巫师$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

可以通过以下方式达到最大总伤害：

• 第一次法术中，使用$a_1=1,\\, b_1=1$，将$X$和$Y$的魔法能量都增加到$1$。
• 第二次法术中，使用$c_2=2,\\, d_2=2$，共造成2点伤害。
• 第三次法术中，使用$a_3=2,\\, b_3=1$，$X$ 的法术造成1点伤害并将 $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

以魔法能量为 $0$ 施放法术 $2$ 不造成伤害。

示例输入 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