配点 : $1000$ 点

問題文

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

制約

• $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$

出力

答えを出力せよ。

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

3

次のようにすると最大値を達成出来ます。

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

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

0

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

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