P7097 [yLOI2020] Marionette Play

> In the wind and snow, autumn-white hair ends faintly show; lights glow lushly, wrinkling your brows. > If you give up a tear, if I grow old, I can stay with you. > Turn to ash in the misty waves, yet still leave perfectly. > > — Yinlin & Aki Ajie, “牵丝戏”.

Fusu and Fugugu have recently been playing a game called “ddt”. Because “牵丝戏” is played on repeat while playing “ddt”, whenever they think of “牵丝戏”, they think of this game. To simplify the problem, we consider it a 1v1 turn-based game. Each player has an attribute called the delay value, abbreviated as the $d$ value. The $d$ value increases according to the types and quantities of items the player uses during a turn. We define player $x$’s turn as the whole process from launching an attack to the end of that turn. **During player $x$’s turn, only player $x$ can use items and attack, and player $x$ will definitely attack.** After a player’s turn ends, the next turn belongs to the player whose $d$ value is **smaller**. If the two players’ $d$ values are equal, since Fusu pays a lot, the next turn is definitely **Fusu’s turn**. There are $m$ kinds of items in this game. Using the $i$-th item increases the damage of this turn by $\frac{k_i}{10^5}$ times the **base damage that does not count other items**, and also increases the $d$ value by $p_i$. In each turn, **each kind of item can be used at most once, and items used in this turn do not provide any damage bonus to the next turn**. Also, after each turn ends, the attacking player’s $d$ value will definitely increase by $w$. Item usage is restricted by the difference between the two players’ $d$ values. Specifically, in any turn, the items used must ensure that after the turn ends, the absolute difference between the two players’ $d$ values (including the guaranteed $w$ increase to the attacking player’s $d$ value) is **no more than** $100$. An obvious fact is that as long as $w \le 100$, a player will always have some way to choose items (including choosing none) to satisfy this restriction. For example, in Fugugu’s turn, if her base damage is $t=10^5$, her initial $d$ value is $d_0=3$, and $w=2$, and she uses two items with $k_1=114$, $k_2=514$, $p_1=19$, $p_2=81$, then the damage she deals this turn is $$t + t \times k_1 + t \times k_2 = 10^5 + 114 + 514 = 100628$$ Her $d$ value after the turn ends is $$d_0 + w + p_1 + p_2 = 3 + 2 + 19 + 81 = 105$$ If the next turn is still her turn and she does not use any items, then the damage she deals in the next turn is $$t = 100000$$ Her $d$ value after that next turn ends is $$105 + w = 105 + 2 = 107$$ Now Fusu and Fugugu are fighting. Given the item list of the game, and their base damage and $d$ values, the game will last for a total of $n$ turns. Assume that no matter how much damage is dealt, neither side will die. Please maximize the value of “damage dealt by Fusu to Fugugu $-$ damage dealt by Fugugu to Fusu”. Of course, Fugugu will also try her best to maximize the value of “damage dealt by her to Fusu $-$ damage dealt by Fusu to her”. Assume Fusu is the smartest boy in the yLOI world and Fugugu is the smartest girl in the yLOI world, meaning **they will both choose the optimal strategy to use items and will not make mistakes**. What you need to output is the maximum damage difference under this condition.

The first line contains an integer indicating the subtask index $T$ of this test point. The second line contains three integers: the number of turns $n$, the number of items $m$, and the fixed $d$ increase per turn $w$. The third line contains $m$ integers, where the $i$-th integer is $k_i$. The fourth line contains $m$ integers, where the $i$-th integer is $p_i$. The fifth line contains four integers, in order: Fusu’s initial base damage $x_a$, Fugugu’s initial base damage $x_b$, Fusu’s initial $d$ value $d_a$, and Fugugu’s initial $d$ value $d_b$.

Output one line with one integer, the answer.

### Sample 1 Explanation - Before turn 1 starts, Fusu’s $d$ value is $2$ and Fugugu’s $d$ value is $3$, so turn 1 is Fusu’s. Fusu does not use any items, the damage is $100000$, his $d$ value increases by $1$, and the total damage difference is $100000$. - After turn 1 ends, both players’ $d$ values are $3$, so turn 2 is Fusu’s. Fusu uses the first item, the damage is $100050$, his $d$ value increases by $21$, and the total damage difference is $200050$. - After turn 2 ends, Fusu’s $d$ value is $24$ and Fugugu’s $d$ value is $3$, so turn 3 is Fugugu’s. Fugugu uses items $1$ and $2$, the damage is $200102$, her $d$ value increases by $121$, and the total damage difference is $-52$. After this turn ends, the $d$ value difference is exactly $100$, which satisfies the requirement. ### Constraints and Conventions **This problem uses bundled multiple testdata.** - Subtask $1$ ($5$ points): guaranteed $n=0$. - Subtask $2$ ($10$ points): guaranteed $m=0$. - Subtask $3$ ($15$ points): guaranteed $n,m \le 5$. - Subtask $4$ ($20$ points): guaranteed $n \le 3$. - Subtask $5$ ($20$ points): guaranteed $m \le 10$. - Subtask $6$ ($30$ points): no special constraints. For all test points, it is guaranteed that $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$ and $x_b$ are multiples of $10^5$, $1 \le |d_a-d_b| \le 100$. ### Notes There are 4 sample files in total; please see opera.zip in the additional files. For sample 2, $m = 0$. For sample 3, $n \leq 3$. Translated by ChatGPT 5