Optimal Damage Difference in the ddt Game

Two brilliant players, FuSu and FuGuGu, are playing a one‐on‐one, turn‐based game called ddt. In this game each player has a delay value \(d\). At the beginning of the game FuSu has rate of \(t_1\) and initial delay \(d_1\), while FuGuGu has rate \(t_2\) and delay \(d_2\). The game lasts for \(n\) rounds. In each round, only the player whose turn it is may use any subset of items and then launch an attack. Note that each player must attack on his turn and may use each available item at most once in that round.

There are \(m\) items. The \(i\)th item, when used, increases the attack damage of that round only by a factor of \(\frac{k_i}{10^5}\) multiplied by the player’s base damage, and adds \(p_i\) points to the delay \(d\) (affecting the turn‐order in later rounds). In addition, after every round the attacking player always gains \(w\) delay points. Thus if a player with base damage \(t\) uses items whose total bonus factors sum up to \(K\) (i.e. \(K=\sum_{i\in S} k_i\)) and total delay addition \(P=\sum_{i\in S} p_i\), then his damage in that round will be \[ t\times \Bigl(1+\frac{K}{10^5}\Bigr)=t+\frac{t\,K}{10^5}, \]

and his delay increases by [ d + w + P. ]

The twist: The items used in any round are subject to a delay‐difference restriction. Suppose that at the start of a player’s turn the two players have delay values \(d_x\) (the attacker) and \(d_y\) (the defender). If the attacker uses a set of items with total delay addition \(P\), then after adding the mandatory \(w\) delay the attacker’s new delay becomes \(d_x+w+P\). It must hold that \[ \bigl|\, (d_x+w+P) - d_y \bigr| \le 100. \] In other words, the attacker must choose his items so that after his turn the two players’ delays differ by at most 100.

The turn order is then determined by comparing the players’ delay values: the player with the smaller delay attacks next; in case of a tie, it is FuSu’s turn.

Both players are extremely clever. FuSu wishes to maximize the overall value \[ \Bigl(\text{total damage dealt by FuSu to FuGuGu}\Bigr) - \Bigl(\text{total damage dealt by FuGuGu to FuSu}\Bigr), \] while FuGuGu wishes to maximize the negative of that expression. Assuming that in every round each player chooses an optimal subset of items (possibly choosing none) under the delay‐difference constraint, compute the final damage difference when both play optimally.

Additional details:

• In every round the attacking player must launch an attack.
• The damage bonus from items applies only for the current round.
• Each item can be used at most once per round (but is available in every round).
• The delay‐difference constraint for a move is as follows:

If the current state has delay difference \(\delta = d_{\text{FuSu}} - d_{\text{FuGuGu}}\) and the attacking player is:

• FuSu: his chosen items (with total delay \(P\)) must satisfy \[ -100 \le \delta + w + P \le 100. \]
• FuGuGu: her chosen items (with total delay \(P\)) must satisfy \[ -100 \le w+P - \delta \le 100. \]

The immediate reward in a round is calculated as:

• If FuSu attacks: \(t_1+\frac{t_1\,K}{10^5}\).
• If FuGuGu attacks: \(-\Bigl(t_2+\frac{t_2\,K}{10^5}\Bigr)\) (since it hurts FuSu’s overall difference).

After the move, the attacker’s delay increases by \(w+P\) while the defender’s delay remains unchanged. Then the next turn is given to the player with the smaller delay value, with FuSu acting in case of a tie.

The input provides \(n\), \(m\), \(w\), the players’ base damages and initial delays, followed by \(m\) lines each containing two integers \(k_i\) and \(p_i\). It is guaranteed that \(w \le 100\), ensuring that at least one valid move (using no items) always exists.

Your task is to compute the final optimal damage difference (i.e. FuSu’s total damage minus FuGuGu’s total damage) when both players play optimally.

inputFormat

The first line contains three integers \(n\), \(m\), and \(w\) — the number of rounds, the number of items, and the fixed delay increment per round.

The second line contains two integers \(t_1\) and \(d_1\) — FuSu’s base damage and initial delay.

The third line contains two integers \(t_2\) and \(d_2\) — FuGuGu’s base damage and initial delay.

Then \(m\) lines follow. The \(i\)th of these lines contains two integers \(k_i\) and \(p_i\) describing the \(i\)th item.

Note: It is guaranteed that \(w \le 100\) and that a valid move always exists.

outputFormat

Output a single integer, which is the final damage difference (FuSu’s total damage minus FuGuGu’s total damage) assuming optimal play from both players.

sample

1 2 2
100000 3
100000 103
114 19
514 81

100628