嘉豪体重已经突破了200，没错，单位是千克。嘉豪认为这会有损他的魅力，于是他设计了 n 天的减肥计划。

在接下来的 n 天里，假设在第 i 天，嘉豪摄入了 r_i 卡路里，并代谢了 c_i 克的体重。根据嘉豪的体质，今天代谢的体重应该是 c_i = p × c_{i-1} + (1 - p) × r_{i - 1} 嘉豪对自己了如指掌，其中参数 r_0 、c_0 和 p(0 < p < 1)嘉豪已经知道了。

当然，嘉豪自制力非常差，他不会完全按照预先的减肥计划进行。在 n 天中有 k 天，嘉豪会暴饮暴食，这些天消耗的卡路里数量是确定的。另外的，嘉豪每天摄入的热量都会在区间 [L, R] 内，不论是否暴饮暴食，也就是说任意的 r_i∈[L, R]。

在满足上述条件的情况下，嘉豪希望安排 n 天的减肥计划，以保证最大化消耗的和摄入的总差值，也就是max\sum_{i = 1}^{n}(c_i - r_i)。

第一行包含一个整数 T \quad (1 ≤ T ≤ 10^3)，表示测试用例的数量。每个测试用例按如下方式给出：

第一行包含两个整数 n 和 k \quad (1 ≤ k ≤ n ≤ 10^5, 1 ≤ \sum n ≤ 2×10^5)。

第二行包含五个实数：r_0、c_0、p、L、R \quad (1 ≤ L ≤ r_0 ≤ R ≤ 10^9, 0 < p < 1, 1 ≤ c_0 ≤ 10^9)。

接下来 k 行，每行包含一个整数 x_i \quad (1\leq x_i\leq n,\forall i\neq j,x_i\neq x_j) 和一个实数 v_i \quad (L\leq v_i\leq R)。表示 r_{x_i} 的值为 v_i。

确保所有输入的实数最多有 6 位小数。

对每个测试用例，输出一行，包含一个实数，表示从第 1 天到第 n 天，每天的代谢质量与当天摄入热量之差的总和的最大值。如果您的答案与正确答案的绝对值或相对值之差不超过 10^{-6}，则被视为正确答案。