题目描述

牛棚里有 \(N\) 头奶牛 \((1≤N≤20,000)\)，它们对室内温度非常敏感。其中奶牛 \(i\) 只能适应 \(A(i)\) 到 \(B(i)\) 这一区间的室温 \((0≤A(i)≤B(i)≤10^9)\)。管理员通过设定恒温器的温度来控制室温，显然管理员可以任意设定恒温器温度（温度值一定为整数）。如果管理员设定的室温 \(T\) 小于 \(A(i)\)，奶牛 \(i\) 就会觉得冷，相应的产奶量就会变为 \(X\)；如果管理员设定的室温 \(T\) 正好在 \(A(i)\) 到 \(B(i)\) 这一区间，即 \(A(i)≤T≤B(i)\)。奶牛 \(i\) 就会觉得很舒适，相应的产奶量就会变为 \(Y\)；如果管理员设定的室温 \(T\) 大于 \(B(i)\)，奶牛 \(i\) 就会觉得热，相应的产奶量就会变为 \(Z\)。当然，\(Y\) 一定大于 \(X\) 和 \(Z\)。
现在告诉你 \(X、Y\) 和 \(Z\) 的值以及每头奶牛能适应的室温区间，请帮助管理员设定好牛棚内的最佳室温以获得最大的产奶量。 \(X、Y\) 和 \(Z\) 都是范围在 \(0\) 到 \(1000\) 之内的整数。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为四个整数 \(N,X,Y,Z\)；第二行到第 \(N+1\) 行，每行两个整数 \(A(i)\) 和 \(B(i)\)。

输出格式

输出一个整数，表示设定好牛棚内的最佳室温后获得的最大的产奶量。

样例1

输入样例1

1
4 7 9 6
5 8
3 4
13 20
7 10

输出样例1

31

样例解释

管理员将室温设置为 \(7\) 或 \(8\)，这样，\(1\) 和 \(4\) 号奶牛感到舒适。\(2\) 号奶牛太热而 \(3\) 号奶牛太冷，总的产奶量是 \(2×9+7+6=31\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("milktemp.in","r",stdin);
freopen("milktemp.out","w",stdout);