AT_arc142_f [ARC142F] Paired Wizards

有两位魔法使 $X$ 和 $Y$ 正在与怪物战斗。 一开始，两人的魔力均为 $0$。他们都掌握以下两种魔法： - 魔法 $1$：使用者的魔力增加 $1$。 - 魔法 $2$：对怪物造成等同于使用者当前魔力的伤害。 两人各自使用 $N$ 次魔法后撤退。 对于每一次 $i=1,\ldots,N$，两人可以选择以下两种魔法组合之一： - $X$ 使用魔法 $a_i$，$Y$ 使用魔法 $b_i$。 - $X$ 使用魔法 $c_i$，$Y$ 使用魔法 $d_i$。 请你求出在两人撤退前，对怪物造成的总伤害的最大值。

输入以如下格式从标准输入读入。 > $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\}$ - 输入均为整数 ## 样例解释 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$。 ## 样例解释 2 如果魔力为 $0$ 时使用魔法 $2$，则无法造成伤害。 由 ChatGPT 4.1 翻译