Alice and Bob are playing the co-op video game Glacier Adventure from UFD 50, a compilation of retro-inspired edutainment games! Alice and Bob control a shared character, Penchick, and they need to help Penchick scale an ice shelf. The twist of the game is that the actions available to each player (to control Penchick) are different.
The ice shelf extends infinitely to the east and to the north, and is subdivided into rows and columns. The ice shelf does have a south-west-most corner, which we denote by $$$(1, 1)$$$. In general, let the cell in the $$$x'$$$th column from the left and $$$y'$$$th row from the bottom be denoted by $$$(x', y')$$$.
Penchick's current coordinates shall be denoted by the value $$$(x, y)$$$, and its initial value is $$$(x_s, y_s)$$$. Consider the set of all cells that Penchick can reach from its current position by only going west and south—the size of this set is called Penchick's score, and the objective of the game is to maximize this score.
For example, in the following position, Penchick's initial coordinates have $$$x_s = 6$$$ and $$$y_s=3$$$, and Penchick's score is $$$18$$$. If Penchick moves $$$1$$$ step east and $$$2$$$ steps north, Penchick's position updates from $$$(x, y) = (6, 3)$$$ into $$$(x, y) = (7, 5)$$$, and the score improves to $$$35$$$.
Credits to Aldrich Asuncion Alice can move penchick using Action Cards. There are $$$n$$$ cards, labeled $$$1$$$ to $$$n$$$. When Alice uses card $$$i$$$, Penchick moves $$$+x_i$$$ steps east and $$$+y_i$$$ steps north. However, each card can only be used at most once, and also only at most $$$p$$$ of these cards can be used overall.
Bob, on the other hand, has three different special abilities to choose from.
- Balance, which simultaneously sets Penchick's $$$x$$$ and $$$y$$$ coordinates to their average ($$$x$$$ rounded up, $$$y$$$ rounded down). Precisely, it simultaneously assigns $$$x = \left\lceil \dfrac{x + y}{2} \right\rceil$$$ and $$$y = \left\lfloor \dfrac{x + y}{2} \right\rfloor$$$.
- Bob can use this skill up to $$$100$$$ times.
- Climb, which moves Penchick $$$c$$$ steps west and $$$c$$$ steps north (where $$$c$$$ is a given fixed constant).
- Bob can use this skill up to $$$5$$$ times.
- Dive, which moves Penchick $$$d$$$ steps east and $$$d$$$ steps south (where $$$d$$$ is a given fixed constant).
- Bob can use this skill up to $$$42$$$ times.
Alice and Bob can collaborate, and can perform any sequence of actions, in any order. What is the maximum possible value of Penchick's score that can be attained?
The first line of input contains a single integer $$$T$$$, denoting the number of test cases. The descriptions of $$$T$$$ test cases follow.
The first line of each test case contains six space-separated integers: $$$n$$$ and $$$p$$$ (the number of Action Cards, and the maximum total number of Action Cards that can be used), $$$x_s$$$ and $$$y_s$$$ (Penchick's initial coordinates), and $$$c$$$ and $$$d$$$ (the "step size" of the Climb and Dive abilities).
The next $$$n$$$ lines describe the Action Cards available to Alice. The $$$i$$$th of these lines contains the two space-separated integers $$$x_i$$$ and $$$y_i$$$, describing the effect of card $$$i$$$.
For each test case, output one line containing a single integer denoting the answer for that test case. Note that the answer might be quite large... beware integer overflow.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 100 \\ 1 \leq x_s, y_s, c, d \leq 10^6 \\ 1 \leq p \leq n \le 3000 \\ \text{$1 \leq x_i, y_i \leq 10^6$ for all $i$} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{60} & \text{$n \leq 6$} \\ && \text{$x_s, y_s, c, d \leq 5$} \\ && \text{$x_i, y_i \leq 5$ for all $i$} \\ \hline 2 & \mathbf{15} & n \leq 6 \\ \hline 3 & \mathbf{10} & n \leq 80 \\ \hline 4 & \mathbf{10} & n \leq 300 \\ \hline 5 & \mathbf{5} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
1 4 2 15 18 6 9 21 23 8 12 20 10 4 19
2862
Penchick's initial coordinates are $$$(15, 18)$$$. Here is one possible sequence of actions that yields the maximum score:
- Alice uses card $$$3$$$. Penchick's new coordinates are $$$(35, 28)$$$.
- Bob performs a climb. Penchick's new coordinates are $$$(29, 34)$$$.
- Bob performs a dive. Penchick's new coordinates are $$$(38, 25)$$$.
- Alice uses card $$$1$$$. Penchick's new coordinates are $$$(59, 48)$$$.
- Bob performs a climb. Penchick's new coordinates are $$$(53, 54)$$$.
