题目背景

对立从那灰暗的塔楼进入，逐步踏入这个扭曲的迷宫深处。

对立的心突然绞痛起来。

对立后退了一步，扑腾了一下便跪倒下来。

未及碰到，灰黑的地板就突然崩裂瓦解，先一步向下坠落。

先前收集的纷争碎片，连同塔楼本身，一同化作了一场倾盆大雨，包围在对立四周。

异象骤起，对立的思维也陷入一片混乱。

塔楼落入了先前的由光芒碎片组成的欢乐海洋，但对立却被纷争碎片紧紧地包裹着。

在那由光芒和纷争碎片交错的风暴之中，对立所见的只有那些令人厌恶的纷争碎片。

那枚世界尽头的记忆映入了对立的视野。

面对着世界一点点地走向终结的景象，对立的理性在碎裂。

对立意识到，一切美好的记忆不过是须臾，最终都会走向破灭。

四周的碎片依旧在飞旋，对立试图看清那些玻璃碎片的变换。

对立意识到，现在围绕着的那些碎片，正以最恐怖的方式运转。

这个碎片风暴所带来的「忧郁度」，可以被简单地描述为外侧碎片的旋转速度之和乘上内侧碎片的旋转速度之和。

一片玻璃碎片在外侧总是以一种速度正旋，而在内侧总是以另一种速度逆旋。

每片碎片都是是来自不同世界的刹那记忆，故而其转速总可以认为是独立随机指定的。

在残存无几的希望将尽未尽之时，对立只想知道，现在的碎片风暴的忧郁度，也就是最大可能的忧郁度，究竟是多少。

题目描述

共有 $n$ 个元素，标号 $1\sim n$，每个元素 $j$ 有两个正整数权值 $a_j,b_j$。

你要确定一个 $[1,n]\cap\mathbb N$ 的子集 $S$，从而最大化

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

这个问题显然不可做，因此保证每个 $a_j,b_j$ 分别在 $[1,A]\cap\mathbb N,[1,B]\cap\mathbb N$ 内独立均匀随机生成。

现在给定 $n,A,B$ 和每个元素的两个权值 $(a_j,b_j)$，请求出这个最大的答案。

输入格式

本题每个测试点中有多组测试数据。

第一行四个整数，$T,n,A,B$，$T$ 表示该组数据内的数据组数，$n,A,B$ 表示该测试点内的所有数据均对应此 $n,A,B$。

接下来每组数据占 $n$ 行，其中第 $j$ 行两个整数 $a_j,b_j$。

保证 $a_j,b_j$ 在对应范围内独立均匀随机生成。

输出格式

对于每组数据输出一行一个整数，表示其答案。

注意这个答案可能很大，你可能需要使用 __int128 类型来进行中间存储与运算，并最后输出。注意你可能需要使用一些正确的输出方式。

提示

输入输出样例

因为本题数据规模太大，直接提交评测会对评测机带来很大压力，本题将提供很多大样例；请尽量减少本题的提交次数。

请参见下发文件 grievouslady*.in/ans，共 $50$ 组，基本按照部分分的方法造。

由于本题保证数据随机，不提供手搓样例。

数据范围与提示

对于所有的数据，保证 $10\le n\le3000$，$10^4\le A,B\le10^{12}$，$1\le T\le50$。

本题设置子任务，各子任务共 $100$ 个测试点。具体的测试点分布可以见下表。

本题在洛谷上的版本不设置子任务。

（由于表格比较宽，洛谷上较难完整显示，你可能要使用题目页面的“展开”功能）

测试点编号	$n$	$A$	$B$	测试点编号	$n$	$A$	$B$	测试点编号	$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}$

我们按如下方式布局各测试点：

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

本题不设置子任务依赖，因此请确保经样例测试后你的算法正确后再提交，以免卡评测机。

后记

这个世界——一切——都源于过去。过去的影像，哪怕是欢乐的记忆，就像是白昼过后的黑夜，渐渐导致了这份世界末日。

泪水盈眶。对立的眼神转为一片黑暗。

对立与这些玻璃起了共鸣，围绕于四周的回忆之壳开始崩裂。

对立就身处其中，站在那炫目的光芒前方，已经没有任何情感了。

扭曲的迷宫，也在对立的力量下，悉数损毁……

时光逝去，对立变了。不再激情地收集回忆，而是近乎无意识地走在这世界之中，并不再抱有任何雄心壮志。

如今，对立正在一个破旧坍塌的建筑旁行走着，旋转着某天在废墟中找到的太阳伞。