Background

Tairitsu entered from that gloomy tower, step by step going deeper into this twisted maze.

A sudden stabbing pain struck Tairitsu’s heart.

Tairitsu stepped back, stumbled, and then fell to their knees.

Before Tairitsu could even touch it, the dark gray-black floor suddenly cracked and collapsed, falling downward first.

The conflict fragments collected earlier, together with the tower itself, turned into a torrential rain, surrounding Tairitsu.

A strange phenomenon suddenly appeared, and Tairitsu’s mind fell into chaos.

The tower fell into the joyful ocean made of light fragments from before, but Tairitsu was tightly wrapped by conflict fragments.

Within the storm where light and conflict fragments intertwined, the only things Tairitsu could see were those disgusting conflict fragments.

That memory from the end of the world came into Tairitsu’s sight.

Facing the scene of the world slowly moving toward its end, Tairitsu’s reason was shattering.

Tairitsu realized that all beautiful memories are only for a moment, and in the end they will all head toward destruction.

The fragments around were still swirling, and Tairitsu tried to see clearly the changes of those glass fragments.

Tairitsu realized that the fragments surrounding them were now operating in the most terrifying way.

The “melancholy level” brought 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 spins forward at one speed on the outer side, and always spins backward at another speed on the inner side.

Each fragment is an instant memory from a different world, so its rotation speeds can always be considered as independently randomly assigned.

When the little remaining hope was about to be completely extinguished, Tairitsu only wanted to know: for the current fragment storm, what exactly is the melancholy level, that is, the maximum possible melancholy level?

Problem Description

There are $n$ elements, numbered $1\sim n$. Each element $j$ has two positive integer weights $a_j,b_j$.

You need to determine a subset $S$ of $[1,n]\cap\mathbb N$ to maximize

$$\left(\sum_{k=1}^na_k[k\in S]\right)\left(\sum_{k=1}^nb_k[k\notin S]\right)$$

This problem is obviously infeasible, so it is guaranteed that each $a_j,b_j$ is generated independently and uniformly at random within $[1,A]\cap\mathbb N$ and $[1,B]\cap\mathbb N$, respectively.

Now given $n,A,B$ and the two weights $(a_j,b_j)$ of each element, please compute the maximum answer.

Input Format

There are multiple sets of testdata in each test point.

The first line contains four integers $T,n,A,B$. $T$ denotes the number of datasets in this group, and $n,A,B$ indicate that all datasets in this test point share the same $n,A,B$.

Then each dataset consists of $n$ lines. In the $j$-th line there are two integers $a_j,b_j$.

It is guaranteed that $a_j,b_j$ are generated independently and uniformly at random within the corresponding ranges.

Output Format

For each dataset, output one integer per line, which is the answer.

Note that the answer may be very large. You may need to use the __int128 type for intermediate storage and computation, and then print the result. Note that you may need to use some correct output methods.

Hint

Sample I/O

Because the data size of this problem is too large, submitting directly for judging will put a lot of pressure on the judge machine. This problem will provide many large samples; please try to reduce the number of submissions.

Please refer to the attached files grievouslady*.in/ans, a total of $50$ groups, basically generated according to the partial-score approach.

Since this problem guarantees random data, no hand-written samples are provided.

Constraints and Hints

For all data, it is guaranteed that $10\le n\le3000$, $10^4\le A,B\le10^{12}$, $1\le T\le50$.

This problem has subtasks; there are a total of $100$ test points. The detailed distribution of test points can be seen in the table below.

The version of this problem on Luogu does not have subtasks.

(Because the table is relatively wide, it is hard to display it completely on Luogu. You may need to use the “Expand” function on the problem page.)

Test Point ID	$n$	$A$	$B$	Test Point ID	$n$	$A$	$B$	Test Point ID	$n$	$A$	$B$
$1\sim2$	$=10$	$=10^4$		$33\sim34$	$=100$	$=10^4$		$67\sim68$	$=1000$	$=10^5$	$=10^{12}$
$3\sim4$		$=10^9$		$35\sim36$		$=10^5$	$=10^5$	$69\sim70$		$=10^9$
$5\sim6$		$=10^{12}$		$37\sim38$			$=10^9$	$71\sim72$		$=10^{12}$	$=10^{12}$
$7\sim8$	$=20$	$=10^4$		$39\sim40$		$=10^9$		$73\sim74$	$=1500$	$=10^5$
$9\sim10$		$=10^9$		$41\sim42$		$=10^{12}$	$=10^{12}$	$75\sim76$		$=10^9$
$11\sim12$		$=10^{12}$		$43\sim44$	$=200$	$=10^5$		$77\sim78$		$=10^{12}$	$=10^{12}$
$13\sim14$	$=30$	$=10^4$		$45\sim46$		$=10^9$		$79\sim80$	$=2000$	$=10^5$
$15\sim16$		$=10^9$		$47\sim48$		$=10^{12}$	$=10^{12}$	$81\sim82$		$=10^9$
$17\sim18$		$=10^{12}$		$49\sim50$	$=300$	$=10^5$		$83\sim84$		$=10^{12}$
$19\sim20$	$=40$	$=10^4$		$51\sim52$		$=10^9$		$85\sim86$	$=2500$	$=10^4$	$=10^9$
$21\sim22$		$=10^9$		$53\sim54$		$=10^{12}$	$=10^{12}$	$87\sim88$		$=10^5$	$=10^{12}$
$23\sim24$		$=10^{12}$		$55\sim56$	$=500$	$=10^5$		$89\sim90$		$=10^9$
$25\sim26$	$=50$	$=10^4$	$=10^4$	$57\sim58$		$=10^9$		$91\sim92$		$=10^{12}$
$27\sim28$			$=10^9$	$59\sim60$		$=10^{12}$	$=10^{12}$	$93\sim94$	$=3000$	$=10^4$	$=10^9$
$29\sim30$		$=10^9$		$61\sim62$	$=800$	$=10^5$		$95\sim96$		$=10^5$	$=10^{12}$
$31\sim32$		$=10^{12}$		$63\sim64$		$=10^9$		$97\sim98$		$=10^9$
				$65\sim66$		$=10^{12}$		$99\sim100$		$=10^{12}$

We arrange the test points in the following way:

• subtask $1$: $1\sim12$, worth $\rm12pts$.
• subtask $2$: $13\sim32$, worth $\rm20pts$.
• subtask $3$: $33\sim36$, worth $\rm4pts$.
• subtask $4$: $37\sim48$, worth $\rm12pts$.
• subtask $5$: $49\sim50$, worth $\rm2pts$.
• subtask $6$: $51\sim60$, worth $\rm10pts$.
• subtask $7$: $61\sim72$, worth $\rm12pts$.
• subtask $8$: $73\sim84$, worth $\rm12pts$.
• subtask $9$: $85\sim92$, worth $\rm8pts$.
• subtask $10$: $93\sim100$, worth $\rm8pts$.

This problem has no subtask dependencies, so please make sure your algorithm is correct after testing on samples before submitting, to avoid stressing the judge machine.

Epilogue

This world—everything—comes from the past. Images of the past, even joyful memories, are like the night after day, gradually leading to this apocalypse.

Tears filled their eyes. Tairitsu’s gaze turned into darkness.

Tairitsu resonated with these shards of glass, and the shell of memories swirling around began to crack.

Tairitsu stood within it, in front of that dazzling light, already without any feelings.

The twisted maze, under Tairitsu’s power, was completely destroyed...

As time passed, Tairitsu changed. No longer passionately collecting memories, but walking through this world almost unconsciously, and no longer holding any ambition.

Now, Tairitsu is walking beside a ruined collapsed building, spinning a parasol that was once found in the rubble.

Input Format

There are multiple sets of testdata in each test point.

The first line contains four integers, $T,n,A,B$. $T$ denotes the number of datasets in this group, and $n,A,B$ indicate that all datasets in this test point share the same $n,A,B$.

Then each dataset consists of $n$ lines, where the $j$-th line contains two integers $a_j,b_j$.

It is guaranteed that $a_j,b_j$ are generated independently and uniformly at random within the corresponding ranges.

Output Format

For each dataset, output one line containing one integer, representing the answer.

Note that this answer may be very large. You may need to use the __int128 type for intermediate storage and computation, and finally print it. Note that you may need to use some correct output methods.

Hint

Sample I/O

Because the data size of this problem is too large, submitting directly for judging will put a lot of pressure on the judge machine. This problem will provide many large samples; please try to reduce the number of submissions.

Please refer to the attached files grievouslady*.in/ans, a total of $50$ groups, basically generated according to the partial-score approach.

Since this problem guarantees random data, no hand-written samples are provided.

Constraints and Hints

For all data, it is guaranteed that $10\le n\le3000$, $10^4\le A,B\le10^{12}$, $1\le T\le50$.

This problem has subtasks; there are a total of $100$ test points. The detailed test point distribution can be found in the table above.

The version of this problem on Luogu does not have subtasks.

Translated by ChatGPT 5