AT_arc142_f [ARC142F] Paired Wizards

[problemUrl]: https://atcoder.jp/contests/arc142/tasks/arc142_f $ 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 $

答えを出力せよ。

### 制約 - $ 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 $ を使ってもダメージを与えられません。