{"problem":{"name":"Paired Wizards","description":{"content":"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 b","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc142_f"},"statements":[{"statement_type":"Markdown","content":"Two wizards, $X$ and $Y$, are fighting with a monster.\nInitially, each of the wizards has a magic power of $0$. They know the following two spells.\n\n*   Spell $1$: Increases the caster's magic power by $1$.\n*   Spell $2$: Deals damage equal to the caster's magic power to the monster.\n\nAfter each wizard uses a spell $N$ times, they will withdraw from the battle.  \nFor each $i=1, \\ldots, N$, they must use one of the following combinations of spells for their $i$\\-th spells.\n\n*   $X$ casts Spell $a_i$, and $Y$ casts Spell $b_i$.\n*   $X$ casts Spell $c_i$, and $Y$ casts Spell $d_i$.\n\nFind the maximum total damage that can be dealt to the monster before the withdrawal.\n\n## Constraints\n\n*   $1 \\leq N \\leq 8000$\n*   $a_i,b_i,c_i,d_i \\in {1,2}$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$ $c_1$ $d_1$\n$\\vdots$\n$a_N$ $b_N$ $c_N$ $d_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc142_f","tags":[],"sample_group":[["3\n1 1 2 2\n2 1 2 2\n2 1 1 1","3\n\nThe maximum total damage can be achieved as follows.\n\n*   As the $1$\\-st spells, use $a_1=1,\\, b_1=1$, increasing both $X$'s and $Y$'s magic powers to $1$.\n*   As the $2$\\-nd spells, use $c_2=2,\\, d_2=2$, dealing $2$ points of damage in total.\n*   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$."],["5\n2 2 2 2\n2 2 2 2\n2 2 2 2\n2 2 2 2\n2 2 2 2","0\n\nCasting Spell $2$ with a magic power of $0$ deals no damage."],["8\n1 1 2 2\n2 2 2 1\n1 1 2 1\n1 1 2 2\n2 1 1 1\n1 2 1 2\n2 1 1 2\n2 1 2 1","20"],["20\n2 1 2 1\n2 1 1 1\n1 2 1 1\n2 2 1 2\n2 2 2 1\n1 1 2 1\n1 2 2 2\n2 2 2 1\n1 1 1 2\n1 2 1 2\n1 2 2 2\n2 1 1 2\n2 1 1 1\n1 2 1 2\n1 2 1 2\n1 1 1 2\n1 1 2 1\n2 2 1 1\n1 2 2 2\n2 1 1 2","138"]],"created_at":"2026-03-03 11:01:14"}}