题目描述

牛棚里有 $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);