[yLOI2020] 牵丝戏

> 风雪依稀秋白发尾， 灯火葳蕤，揉皱你眼眉。 > 假如你舍一滴泪，假如老去我能陪。 > 烟波里成灰，也去得完美。 ——银临 & Aki阿杰《牵丝戏》

扶苏和扶咕咕最近在玩一款叫做「ddt」的游戏，因为玩「ddt」时一直在循环《牵丝戏》，所以想到牵丝戏就想到了这个游戏。 为了简化问题，我们认为这是一款一对一回合制游戏。双方玩家各有一个属性，被称为 delay 值，简称 $d$ 值。$d$ 值会根据回合中玩家使用的道具类型和数量来进行相应的增加。我们定义玩家 $x$ 的回合为玩家 $x$ 从发动攻击到结束的整个过程。**在玩家 $x$ 的回合中，只有玩家 $x$ 可以使用道具和发动攻击，并且玩家 $x$ 一定会发动攻击**。当一个玩家的回合结束以后，下一回合将是两个玩家中 $d$ 值**较小**的玩家的回合。当两个玩家的 $d$ 值相同时，因为扶苏氪金很多，下一回合一定是**扶苏的回合**。 这款游戏共有 $m$ 种道具，第 $i$ 种道具会将本回合的伤害增加**不计算其他道具的原始伤害**的 $\frac{k_i}{10^5}$ 倍，同时会增加 $p_i$ 点 $d$ 值。每回合**每种道具只能使用一次，本回合的道具不会对下回合产生伤害增益效果**。同时，每回合结束以后，发动攻击的玩家一定会增加 $w$ 点 $d$ 值。 而使用道具是受到双方 $d$ 值差限制的。具体的，任何回合所使用的道具应该满足本回合结束以后双方 $d$ 值（包括发动攻击的玩家一定增加的 $w$ 点 $d$ 值）之差的绝对值**不超过** $100$。一个显然的事实是，只要保证了 $w \le 100$，玩家就一定存在一种选择道具的方法（包括不选择），来满足这个限制。 例如，在扶咕咕的回合中，若她的原始伤害 $t=10^5$，初始时 $d$ 值 $d_0=3$，规定 $w=2$，她使用了两个道具，$k_1=114$，$k_2=514$，$p_1=19$，$p_2=81$，那么本回合她造成的伤害为 $$t + t \times k_1 + t \times k_2 = 10^5 + 114 + 514 = 100628$$ 她回合结束后的 $d$ 值为 $$d_0 + w + p_1 + p_2 = 3 + 2 + 19 + 81 = 105$$ 而假如下回合还是她的回合，并且她没有使用道具，那么她下回合造成的伤害为 $$t = 100000$$ 她下回合结束后的 $d$ 值为 $$105 + w = 105 + 2 = 107$$ 现在扶苏和扶咕咕正在对战。给定游戏的道具列表，和他们的原始伤害、 $d$ 值。游戏一共会进行 $n$ 回合，不妨认为无论造成多大的伤害，双方都不会死亡。请你最大化「扶苏对扶咕咕造成的伤害 - 扶咕咕对扶苏造成的伤害」这个差的值。 当然，扶咕咕也会尽可能最大化「她对扶苏造成伤害 - 扶苏对她造成伤害」的值。不妨认为扶苏是 yLOI 世界中最聪明的男孩子，扶咕咕是 yLOI 世界中最聪明的女孩子，也就是**他们都会选择最优的策略来使用道具而不会出错**，题目所求即为在这种情况下伤害差的最大值。

第一行有一个整数，表示该测试点所在的子任务编号 $T$。 第二行有三个整数，分别表示游戏的回合数 $n$，游戏的装备数 $m$ 以及每回合固定增加的 $d$ 值 $w$。 第三行有 $m$ 个整数，第 $i$ 个整数表示 $k_i$。 第四行有 $m$ 个整数，第 $i$ 个整数表示 $p_i$。 第五行有四个整数，依次表示扶苏的初始伤害 $x_a$，扶咕咕的初始伤害 $x_b$，扶苏的初始 $d$ 值 $d_a$，扶咕咕的初始 $d$ 值 $d_b$。

输出一行一个整数表示答案。

0
3 2 1
50 1
20 100
100000 200000 2 3

-52

### 样例 1 解释 - 第一回合开始前，扶苏 $d$ 值为 $2$，扶咕咕 $d$ 值为 $3$，第一回合由扶苏出手。扶苏不使用道具，伤害为 $100000$，$d$ 值增加 $1$，总伤害差为 $100000$。 - 第一回合结束后，双方 $d$ 值均为 $3$，第二回合由扶苏出手。扶苏使用第一个道具，伤害为 $100050$，$d$ 值增加 $21$，总伤害差为 $200050$。 - 第二回合结束后，扶苏 $d$ 值为 $24$，扶咕咕 $d$ 值为 $3$，第三回合由扶咕咕出手。扶咕咕使用 $1$ 、 $2$ 两个道具，伤害为 $200102$，$d$ 值增加 $121$，总伤害差为 $-52$。这回合结束后，双方 $d$ 值差恰好为 $100$，符合要求。 ### 数据规模与约定 **本题采用多测试点捆绑测试**。 - 子任务 $1$（$5$ 分）：保证 $n=0$。 - 子任务 $2$（$10$ 分）：保证 $m=0$。 - 子任务 $3$（$15$ 分）：保证 $n,m \le 5$。 - 子任务 $4$（$20$ 分）：保证 $n \le 3$。 - 子任务 $5$（$20$ 分）：保证 $m \le 10$。 - 子任务 $6$（$30$ 分）：无特殊约定。 对于全部的测试点，保证 $0 \le n \le 10^3$，$0 \le m \le 10^5$，$1 \le p_i,w \le 100$，$1 \le x_a,x_b,k_a,d_a,d_b \le 10^9$，$x_a$ 与 $x_b$ 是 $10^5$ 的倍数，$1 \le |d_a-d_b| \le 100$。 ### 提示 共有 4 个样例文件，请见附加文件中的 opera.zip。 对于样例 2，满足 $m = 0$。 对于样例 3，满足 $n \leq 3$。