Description

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

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

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

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

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

Input Format

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

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

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

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

Output Format

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

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

Hint

输入输出样例

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

请参见下发文件 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$。

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

后记

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

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

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

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

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

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

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