201425: [AtCoder]ARC142 F - Paired Wizards

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