F - Paired Wizards 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 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

出力

答えを出力せよ。

入力例 1

3
1 1 2 2
2 1 2 2
2 1 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 になる。

入力例 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

Score : 1000 points

Problem Statement

Two wizards, X and Y, are fighting with a monster.

Initially, each of the wizards has a magic power of 0. They know the following two spells.

  • Spell 1: Increases the caster's magic power by 1.
  • Spell 2: Deals damage equal to the caster's magic power to the monster.

After each wizard uses a spell N times, they will withdraw from the battle.
For each i=1, \ldots, N, they must use one of the following combinations of spells for their i-th spells.

  • X casts Spell a_i, and Y casts Spell b_i.
  • X casts Spell c_i, and Y casts Spell d_i.

Find the maximum total damage that can be dealt to the monster before the withdrawal.

Constraints

  • 1 \leq N \leq 8000
  • a_i,b_i,c_i,d_i \in \{1,2\}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1 c_1 d_1
\vdots
a_N b_N c_N d_N

Output

Print the answer.

Sample Input 1

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

Sample Output 1

3

The maximum total damage can be achieved as follows.

  • As the 1-st spells, use a_1=1,\, b_1=1, increasing both X's and Y's magic powers to 1.
  • As the 2-nd spells, use c_2=2,\, d_2=2, dealing 2 points of damage in total.
  • As the 3-rd spells, use a_3=2,\, b_3=1, dealing 1 point of damage by X's spell and increasing Y's magic power to 2.

Sample Input 2

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

Sample Output 2

0

Casting Spell 2 with a magic power of 0 deals no damage.

Sample Input 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

Sample Output 3

20

Sample Input 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

Sample Output 4

138