Earlier in this year, Bob was incredibly bullish on deer stocks, going all-in on the bet that it would be the beloved meme animal of 2024. Unfortunately for him, local markets can behave differently from international ones, and everyone else at his school is obsessed with penchicks instead, causing the value of his deer stonks to nosedive dramatically.
Still, Bob is contractually obligated to preside over his school's "Deer Club" until the end of the school year.
Deer Club consists of $$$n$$$ deer, and $$$m$$$ caretakers. The job of the caretaker is to pamper each deer for some amount of time.
The $$$i$$$th deer wants to be taken care of for $$$x_i$$$ units of time, straight. It also has a deerness value of $$$d_i$$$.
The $$$j$$$th caretaker will work for $$$y_j$$$ units of time, straight. Each one also has a care value of $$$c_j$$$.
When a deer is being taken care of, it will not leave until its $$$x_i$$$ units of time are up, after which it leaves and does not return. When a caretaker starts their shift, they will not leave until their $$$y_j$$$ units of time are done, and then they will not take another shift after that.
Only one deer can be taken care of at a time, and also only one caretaker can work at a time. Thankfully, $$$\sum x_i = \sum y_j$$$, so all you have to do is schedule an order for the deer to arrive, and also an order for the caretakers to work their shifts.
The happiness of the club at time $$$t$$$ is equal to the product of the deerness value of the deer currently being cared for, and the care value of the caretaker currently working. The overall happiness of Deer Club is equal to the sum of its happiness over all times $$$t=1, 2, 3, \dots$$$ until the end of the final shift.
For example, suppose we have $$$n=3$$$ deer and $$$m=2$$$ caretakers, and we have $$$x = [1, 3, 2]$$$ and $$$d=[3, 4, 1]$$$ and $$$y = [2, 4]$$$ and $$$c = [7, 2]$$$. Note that $$$1 + 3 + 2 = 2 + 4 = 6$$$, so the day lasts for $$$6$$$ units of time. Suppose we schedule the deer and caretakers to arrive in that order, then the scenario would look like this:
The overall happiness of Deer Club would be computed over the $$$6$$$ intervals of time, whose happiness values are: $$$3 \times 7$$$ and $$$4 \times 7$$$ and $$$4 \times 2$$$ and $$$4 \times 2$$$ and $$$1 \times 2$$$ and $$$1 \times 2$$$. This yields a sum of $$$69$$$.
However, if Bob cared more, he could choose a better schedule that makes the happiness even higher. If he wanted to be more spiteful, he could also find a worse schedule that makes the happiness even smaller.
What are the maximum and minimum possible total happinesses of Deer Club, across all possible schedules that Bob could pick?
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 the space-separated integers $$$n$$$ and $$$m$$$.
The second line of each test case contains the $$$n$$$ space-separated integers $$$x_1, x_2, \dots, x_n$$$.
The third line of each test case contains the $$$n$$$ space-separated integers $$$d_1, d_2, \dots, d_n$$$.
The fourth line of each test case contains the $$$m$$$ space-separated integers $$$y_1, y_2, \dots, y_m$$$.
The fifth line of each test case contains the $$$m$$$ space-separated integers $$$c_1, c_2, \dots, c_m$$$.
For each test case, output a line containing two space-separated integers—the maximum and minimum possible total happinesses across all schedules. Note that the answer might be quite large... beware integer overflow.
Let $$$N$$$ and $$$M$$$ be the sum of $$$n$$$ and $$$m$$$ (respectively) across all test cases.
$$$$$$\begin{align*}
&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 1000 \\ 1 \leq n, m \\ N, M \leq 10^5 \\ \text{$1 \leq x_i \leq 10^6$ for all $i$} \\ \text{$1 \leq d_i \leq 10^6$ for all $i$} \\ \text{$1 \leq y_j \leq 10^6$ for all $j$} \\ \text{$1 \leq c_j \leq 10^6$ for all $j$} \\ \text{$\sum x_i = \sum y_i$ in each test case} \\ \hline \end{array}\\
&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{51} & \text{$n, m \leq 4$} \\ && \text{$\sum x_i \leq 10$ in each test case} \\ \hline 2 & \mathbf{17} & n, m \leq 4 \\ \hline 3 & \mathbf{16} & n, m \leq 1000 \\ \hline 4 & \mathbf{16} & \text{No further constraints.} \\ \hline \end{array}\\
\end{align*}$$$$$$
1 3 2 1 3 2 3 4 1 2 4 7 2
74 44
