题目描述
小华是一名天才驯龙师！红龙Dew 是他的客户——她最近偷吃太多火山宝石（龙族最爱零食），胖得飞起来像打醉拳。龙族长老下令："必须科学减肥！"
作为龙类行为学专家，小华深知强制节食会引发龙族逆反心理。果然，Dew 的智能项圈数据显示：未来n 天中已有k 天被标记为「放纵日」（龙族传统节日），这些日子她会按龙族习俗摄入固定量的火山岩烤肉（第pi天的固定摄入vi卡路里）。其余日子虽同意控制饮食，但坚持要求保留在[L,R]区间自主选择食物的权利。
龙族代谢存在能量滞留效应，第i 天减少的卡路里ci满足公式：
$c_i=p ∗ c_{i−1}+(1−p) ∗ r_{i−1}$
初始状态由精密仪器测定：基础代谢c0、基准摄入r0，滞留系数p。
在满足Dew 的饮食要求前提下，小华希望通过合理安排非放纵日食物摄入量
ri∈[L,R]，使得 n 天 Dew 的总减肥效果最好，也就是求 $ \sum ^n _{i=1}$ 的最大值。
输入
第一行整数T 表示测试用例数。
每组用例包含：
1.第一行两个整数 n 和 k ( $1 \le k \le n \le 10^5$， $\sum n \le 5 \times 10^5$)。
2.第二行五个浮点数 r0 , c0 , p, L , R ( $1 \le L \le r0 \le R \le 10^9$， $0 \lt p \lt 1$, $1 \le c0 \le 10^9$)。
3.接下来k 行，每行一个整数pi 和浮点数 vi ($1 \le pi \le n$, $L \le vi \le R $), 其中pi 互不重复，表示第pi天的固定摄入vi卡路里。
保证输入的浮点数均为小数后6位有效数字。
输出
每组样例输出一行一个浮点数，表示代谢和摄入的最大差值，允许$10^{−6}$以内的绝对或相对误差。
样例输入输出
输入#1
复制
2
3 2
5 6 0.5 1 10
1 4
2 5
5 2
10 5 0.5 3 12
1 4
3 6
输出#1
复制
5.1250000000
7.9062500000
提示
【样例解释】
第一组最优解r = [ 5, 4, 5, 1]，对应c = [ 6, 5.5, 4.75, 4.875 ]，差值和= ( 5.5 - 4 ) +( 4.75 - 5 ) + ( 4.875 - 1 ) = 5.125。
注意，答案中没有 c0−r0！
【数据范围】
对于30%的数据，$n \le 100$, $\sum n \le 1000$
对于另外30%的数据，保证 k = n.
对于100%的数据，无特殊限制，范围见【输入格式】