Background

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, “牵丝戏”.

Problem Description

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.

Input Format

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 Format

Output one line with one integer, the answer.

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

-52

Hint

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