P8888 [DMOI-R1] 实验基地

小 A 和小 B 用实验基地全新的装备进行了一场世纪蒟蒻之战。

众所周知，实验基地的武器都是一次性的。现在，小 A 选取了 $n$ 把不同的武器，小 B 也获取了 $m$ 把不同武器。每个人的武器都可以用编号 $1$ 到编号 $n$ 或 $m$ 依次表示，他们将会按此顺序逐个使用武器。 实验仓库记录了所有武器的火力。小 A 的第 $k$ 把武器能爆发出 $a_k$ 的能量，而小 B 的第 $k$ 把武器能爆发出 $b_k$ 的能量。特别的，当小 A 的第 $i$ 把武器与小 B 的第 $j$ 把武器同时使用，会释放 $d_{i,j}$ 的能量。由于某些不可描述的组合的奇效，$a,b,d$ **都可能小于** $0$。 当某人第一个使用了武器，战斗就正式开始，记为第 $1$ 秒，直至某人使用完武器后再无人使用武器,记此时为第 $t$ 秒（$t$ **不为输入数据**）。也就是说，**在第 $1$ 秒和第 $t$ 秒必须有人使用武器，而在 $1$ 至 $t$ 秒内在符合其他条件下，每一秒双方可以选择按顺序使用武器或不使用**。 为了避免打死对方，**双方都不一定使用完武器**。 由于实验基地有发电装置，如果小 A 没有连续使用武器释放能量，而是休息了 $x$ 秒，那么祂将会吸收掉 $Ax+B\ (A,B \in \mathbb{N})$ 的能量。同样，小 B 间隔 $y$ 秒将吸收 $Cy+D\ (C,D \in \mathbb{N})$ 的能量。连续两秒都释放武器间隔时间为 $0$ 秒，以此类推。 为了防止基地被核爆，你需要算出战斗结束后可能释放的最大总能量（可能为负数）。 **若对题目细节有疑惑请先读提示内的额外解释。**

无

无

1. 战斗的开始时间（第 $1$ 秒）为双方某人最先释放出第一个技能的时间，战斗结束时间为双方某人释放出最后一个技能的时间。**结束时间不定**。 2. 技能必须按顺序释放，但**不一定需要在战斗中释放完**。 3. $a,b,d$ 可以为负数，总计能量可能为负，“吸收能量”指总能量减少 $Ax+B$ 或 $Cy+D$，也就是**间隔时总能量一定减少**，而且时间越长减少越多。 4. 本题 IO 量较大，建议使用合适的读入方式。 ### 样例解释： 样例 1：每个人在 $1$ 到 $6$ 秒依次使用自己的编号为 $1$ 到 $6$ 的武器即可取到最大值。 样例 2：小 B 在 $1$ 到 $4$ 秒依次使用自己的编号为 $1$ 到 $4$ 的武器，小 A 在第 $4$ 秒使用自己的 $1$ 号武器可以取到最大值。其中单个武器释放的能量为 $(-2)+(2+3+4+9) = 16$，武器碰撞释放 $d_{1,4} = 4$ 单位的能量，小 A 在前 $3$ 秒吸收了 $A \times 3 + B = 5$ 单位的能量。 ### 数据范围： |Subtask|$n\leq$|$m\leq$|分值| |-|-|-|-| |$1$|$10$|$10$|$20$| |$2$|$500$|$500$|$30$| |$3$|$3000$|$3000$|$50$| **本题采用捆绑测试**，您只有通过了一个 Subtask 中的所有测试点才能得到这个 Subtask 的分数。 对于 $100\%$ 的数据：$0 \le |a_k|,|b_k|,|d_{i,j}|,A,B,C,D \leq 1000$, $1\leq n, m\leq 3000$。