You might not need to find the optimal solution for this problem. To encourage you to earn partial points, we have provided a significant amount of partial credit, making it more likely for you to get a "sign-in" score.
Of course, if you are frustrated with the other problems and cannot piece together a brute-force solution, you are welcome to try and find the optimal solution for this problem.
The time limit for this problem is more than twice that of the standard, but this does not mean you will definitely not be hit by constant-factor overhead. It is also possible that your complexity is simply not efficient enough.
The problem setter estimates the difficulty to be higher than another problem, but in reality, for many people, it might be similar or even easier.
Background
Tairitsu entered from that gloomy tower, gradually stepping into the depths of this twisted labyrinth.
Tairitsu's heart suddenly felt a sharp pain.
Tairitsu took a step back, stumbled, and fell to her knees.
Before she could even touch it, the gray-black floor suddenly crumbled and disintegrated, falling downward first.
The previously collected fragments of conflict, along with the tower itself, turned into a torrential downpour, surrounding Tairitsu.
The anomaly arose suddenly, and Tairitsu's mind fell into chaos.
The tower fell into the ocean of joy previously composed of light fragments, but Tairitsu was tightly wrapped in the fragments of conflict.
In that storm of light and conflict fragments, all Tairitsu could see were those detestable fragments of conflict.
That memory from the end of the world entered Tairitsu's field of vision.
Facing the sight of the world slowly coming to an end, Tairitsu's rationality was shattering.
Tairitsu realized that all beautiful memories were but fleeting moments, eventually destined to perish.
The surrounding fragments continued to swirl, and Tairitsu tried to see the transformation of those glass fragments clearly.
Tairitsu realized that the fragments surrounding her now were operating in the most terrifying way.
The "melancholy" brought about by this fragment storm can be simply described as the sum of the rotation speeds of the outer fragments multiplied by the sum of the rotation speeds of the inner fragments.
A glass fragment always rotates forward at one speed on the outside and backward at another speed on the inside.
Each fragment is a fleeting memory from a different world, so its rotation speed can be considered independently and randomly assigned.
As the last remnants of hope were about to vanish, Tairitsu only wanted to know what the melancholy of the current fragment storm—that is, the maximum possible melancholy—actually was.
Description
There are $ n $ elements, labeled $ 1\sim n $. Each element $ j $ has two positive integer weights $ a_j, b_j $.
You need to determine a subset $ S \subseteq \{1, \dots, n\} $ to maximize:
$$(\sum_{k=1}^na_k[k\in S])(\sum_{k=1}^nb_k[k\notin S])$$
This problem is obviously intractable, so it is guaranteed that each $ a_j, b_j $ is independently and uniformly randomly generated within $[1, A] \cap \mathbb N$ and $[1, B] \cap \mathbb N$ respectively.
Given $ n, A, B $ and the two weights $(a_j, b_j)$ for each element, find this maximum answer.
Input
Each test case contains multiple test data sets.
The first line contains four integers $ T, n, A, B $, where $ T $ is the number of data sets, and $ n, A, B $ represent the parameters for all data sets in this test case.
Each of the following $ n $ lines contains two integers $ a_j, b_j $.
It is guaranteed that $ a_j, b_j $ are independently and uniformly randomly generated within their respective ranges.
Output
For each data set, output one integer per line representing the answer.
Note that this answer may be very large; you may need to use the __int128 type for intermediate storage and calculations, and for the final output. Note that you may need to use a correct output method.
Examples
Because the data scale of this problem is very large, submitting directly to the judge will put significant pressure on the system. This problem provides many large sample files; please try to minimize the number of submissions.
Please refer to the provided files grievouslady*.in/ans, which contain 50 sets, basically constructed according to the partial credit methods.
Since this problem guarantees random data, no manual samples are provided.
Constraints
For all data, it is guaranteed that $ 10 \le n \le 3000 $, $ 10^4 \le A, B \le 10^{12} $, and $ 1 \le T \le 50 $.
This problem sets subtasks, with a total of 100 test points across all subtasks. The specific distribution of test points can be seen in the table below.
| Test Point ID | $ n $ | $ A $ | $ B $ | Test Point ID | $ n $ | $ A $ | $ B $ | Test Point ID | $ n $ | $ A $ | $ B $ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $ 1\sim2 $ | $ =10 $ | $ =10^4 $ | $ =10^4 $ | $ 33\sim34 $ | $ =100 $ | $ =10^4 $ | $ =10^4 $ | $ 67\sim68 $ | $ =1000 $ | $ =10^5 $ | $ =10^{12} $ |
| $ 3\sim4 $ | $ =10 $ | $ =10^9 $ | $ =10^9 $ | $ 35\sim36 $ | $ =100 $ | $ =10^5 $ | $ =10^5 $ | $ 69\sim70 $ | $ =1000 $ | $ =10^9 $ | $ =10^9 $ |
| $ 5\sim6 $ | $ =10 $ | $ =10^{12} $ | $ =10^{12} $ | $ 37\sim38 $ | $ =100 $ | $ =10^5 $ | $ =10^9 $ | $ 71\sim72 $ | $ =1000 $ | $ =10^{12} $ | $ =10^{12} $ |
| $ 7\sim8 $ | $ =20 $ | $ =10^4 $ | $ =10^4 $ | $ 39\sim40 $ | $ =100 $ | $ =10^9 $ | $ =10^9 $ | $ 73\sim74 $ | $ =1500 $ | $ =10^5 $ | $ =10^{12} $ |
| $ 9\sim10 $ | $ =20 $ | $ =10^9 $ | $ =10^9 $ | $ 41\sim42 $ | $ =100 $ | $ =10^{12} $ | $ =10^{12} $ | $ 75\sim76 $ | $ =1500 $ | $ =10^9 $ | $ =10^9 $ |
| $ 11\sim12 $ | $ =20 $ | $ =10^{12} $ | $ =10^{12} $ | $ 43\sim44 $ | $ =200 $ | $ =10^5 $ | $ =10^{12} $ | $ 77\sim78 $ | $ =1500 $ | $ =10^{12} $ | $ =10^{12} $ |
| $ 13\sim14 $ | $ =30 $ | $ =10^4 $ | $ =10^4 $ | $ 45\sim46 $ | $ =200 $ | $ =10^9 $ | $ =10^9 $ | $ 79\sim80 $ | $ =2000 $ | $ =10^5 $ | $ =10^{12} $ |
| $ 15\sim16 $ | $ =30 $ | $ =10^9 $ | $ =10^9 $ | $ 47\sim48 $ | $ =200 $ | $ =10^{12} $ | $ =10^{12} $ | $ 81\sim82 $ | $ =2000 $ | $ =10^9 $ | $ =10^9 $ |
| $ 17\sim18 $ | $ =30 $ | $ =10^{12} $ | $ =10^{12} $ | $ 49\sim50 $ | $ =300 $ | $ =10^5 $ | $ =10^{12} $ | $ 83\sim84 $ | $ =2000 $ | $ =10^{12} $ | $ =10^{12} $ |
| $ 19\sim20 $ | $ =40 $ | $ =10^4 $ | $ =10^4 $ | $ 51\sim52 $ | $ =300 $ | $ =10^9 $ | $ =10^9 $ | $ 85\sim86 $ | $ =2500 $ | $ =10^4 $ | $ =10^9 $ |
| $ 21\sim22 $ | $ =40 $ | $ =10^9 $ | $ =10^9 $ | $ 53\sim54 $ | $ =300 $ | $ =10^{12} $ | $ =10^{12} $ | $ 87\sim88 $ | $ =2500 $ | $ =10^5 $ | $ =10^{12} $ |
| $ 23\sim24 $ | $ =40 $ | $ =10^{12} $ | $ =10^{12} $ | $ 55\sim56 $ | $ =500 $ | $ =10^5 $ | $ =10^{12} $ | $ 89\sim90 $ | $ =2500 $ | $ =10^9 $ | $ =10^9 $ |
| $ 25\sim26 $ | $ =50 $ | $ =10^4 $ | $ =10^4 $ | $ 57\sim58 $ | $ =500 $ | $ =10^9 $ | $ =10^9 $ | $ 91\sim92 $ | $ =2500 $ | $ =10^{12} $ | $ =10^{12} $ |
| $ 27\sim28 $ | $ =50 $ | $ =10^4 $ | $ =10^9 $ | $ 59\sim60 $ | $ =500 $ | $ =10^{12} $ | $ =10^{12} $ | $ 93\sim94 $ | $ =3000 $ | $ =10^4 $ | $ =10^9 $ |
| $ 29\sim30 $ | $ =50 $ | $ =10^9 $ | $ =10^9 $ | $ 61\sim62 $ | $ =800 $ | $ =10^5 $ | $ =10^{12} $ | $ 95\sim96 $ | $ =3000 $ | $ =10^5 $ | $ =10^{12} $ |
| $ 31\sim32 $ | $ =50 $ | $ =10^{12} $ | $ =10^{12} $ | $ 63\sim64 $ | $ =800 $ | $ =10^9 $ | $ =10^9 $ | $ 97\sim98 $ | $ =3000 $ | $ =10^9 $ | $ =10^9 $ |
| $ 65\sim66 $ | $ =800 $ | $ =10^{12} $ | $ =10^{12} $ | $ 99\sim100 $ | $ =3000 $ | $ =10^{12} $ | $ =10^{12} $ |
We lay out the test points as follows:
- Subtask 1: $ 1\sim12 $, $ 12 $ pts.
- Subtask 2: $ 13\sim32 $, $ 20 $ pts.
- Subtask 3: $ 33\sim36 $, $ 4 $ pts.
- Subtask 4: $ 37\sim48 $, $ 12 $ pts.
- Subtask 5: $ 49\sim50 $, $ 2 $ pts.
- Subtask 6: $ 51\sim60 $, $ 10 $ pts.
- Subtask 7: $ 61\sim72 $, $ 12 $ pts.
- Subtask 8: $ 73\sim84 $, $ 12 $ pts.
- Subtask 9: $ 85\sim92 $, $ 8 $ pts.
- Subtask 10: $ 93\sim100 $, $ 8 $ pts.
There are no subtask dependencies in this problem, so please ensure your algorithm is correct after testing with the samples before submitting, to avoid putting unnecessary load on the judge.
Note
This world—everything—stems from the past. The images of the past, even joyful memories, are like the night after the day, gradually leading to this end of the world.
Tears welled up in her eyes. Tairitsu's gaze turned into darkness.
Tairitsu resonated with these pieces of glass, and the shells of memories surrounding her began to crumble.
Tairitsu stood right in the middle of it, in front of that dazzling light, devoid of any emotion.
The twisted labyrinth, too, was completely destroyed under Tairitsu's power...
Time passed, and Tairitsu changed. She no longer passionately collected memories, but walked through this world almost unconsciously, no longer harboring any ambition.
Now, Tairitsu is walking past a dilapidated, collapsed building, spinning a parasol she found in the ruins one day.