题目描述

$2$ 人の魔法使い $X,Y$ がモンスターと戦っています。

初め、$2$ 人の魔力はそれぞれ $0$ です。また、以下の $2$ 種類の魔法を習得しています。

• 魔法 $1$ : 使用者の魔力が $1$ 増える。
• 魔法 $2$ : 使用者の魔力と同じだけモンスターにダメージを与える。

$2$ 人はそれぞれ $N$ 回ずつ魔法を使用した後に撤退します。
$i=1,\ldots,N$ に対し、$2$ 人が $i$ 番目に使用する魔法の組み合わせは以下のどちらかです。

• $X$ が魔法 $a_i$ を、$Y$ が魔法 $b_i$ を使用する。
• $X$ が魔法 $c_i$ を、$Y$ が魔法 $d_i$ を使用する。

$2$ 人が撤退するまでにモンスターに与えられるダメージの総和の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $b_1$ $c_1$ $d_1$ $\vdots$ $a_N$ $b_N$ $c_N$ $d_N$

输出格式

答えを出力せよ。

题目大意

有两个魔法师，每个魔法师初始法力值为 $0$。

他们要打怪，怪物初始的伤害值为 $0$。

有两种法术：

• 法术 $1$：给法师的法术加一。

• 法术 $2$：给怪物伤害值加上法师的法力值。

有 $n$ 次选择，每次给定 $a_i,b_i,c_i,d_i$，可以选择：

• 第一个法师使用法术 $a_i$，第二个法师使用法术 $b_i$。

• 第一个法师使用法术 $c_i$，第二个法师使用法术 $d_i$。

最大化怪物的伤害值。

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

3

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

0

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

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\}$
• 入力はすべて整数

Sample Explanation 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$ になる。

Sample Explanation 2

魔力が $0$ の状態で魔法 $2$ を使ってもダメージを与えられません。