Red Dragon Dew's master believes that she has been eating too much recently, causing her to wobble when taking off and reducing her cruising time. Therefore, he ordered her to control her caloric intake.
Over the next $$$n$$$ days, suppose that on the $$$i$$$-th day, Dew consumed $$$r_i$$$ calories and metabolized $$$c_i$$$ grams of mass. According to the characteristics of her dragon species, the mass loss should be $$$c_i = p \times c_{i-1} + (1 - p) \times r_{i-1}$$$, where the parameters $$$r_0$$$, $$$c_0$$$, and $$$p$$$ ($$$0 \lt p \lt 1$$$) have been measured by her master.
Of course, Red Dragon Dew indicated that she would not fully obey commands from her "cook" . She stated that over the next $$$n$$$ days, there are $$$k$$$ days when she will have indulgent meals. The caloric intake on these $$$k$$$ days is predetermined, and the daily caloric intake must be within the range $$$[L, R]$$$, i.e. all $$$r_i$$$ should in range $$$[L,R]$$$.
Given these conditions, Dew wants to arrange the days without indulgent meals to maximize the difference between the total caloric consumption and intake over the next $$$n$$$ days, i.e. $$$\max\sum_{i=1}^n (c_i-r_i)$$$.
Each test case consists of multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10000$$$). The description of the test cases follows:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^5$$$, $$$1 \leq \sum n \leq 2 \times 10^5$$$), indicating that there are $$$n$$$ days ahead, and $$$k$$$ days have predetermined caloric intake.
The second line contains five real numbers $$$r_0$$$, $$$c_0$$$, $$$p$$$, $$$L$$$, and $$$R$$$ ($$$1 \leq L \leq r_0 \leq R \leq 10^9$$$, $$$0 \lt p \lt 1$$$, $$$1 \leq c_0 \leq 10^9$$$), representing the parameters mentioned above.
The next $$$k$$$ lines, each containing an integer $$$p_i$$$ ($$$1 \leq p_i \leq n$$$, $$$\forall i \neq j, p_i \neq p_j$$$) and a real number $$$v_i$$$ ($$$L \leq v_i \leq R$$$), indicating that $$$r_{p_i}$$$ is fixed at $$$v_i$$$.
Ensure that all input real numbers have at most $$$6$$$ decimal places.
For each test case, output the maximum value of $$$\sum_{i=1}^n (c_i - r_i)$$$.
Your answer is considered correct if its absolute or relative difference to the correct answer is at most $$$10^{-6}$$$.
More formally, let $$$a$$$ be your answer and $$$b$$$ be the correct answer. Your output is considered correct if $$$\frac{\left|a-b\right|}{\max(1,b)} \le 10^{-6}$$$.
23 25 6 0.5 1 101 42 55 210 5 0.5 3 121 43 6
5.1250000000 7.9062500000
For the first testcase, one optimal possible $$$r=[5, 4, 5, 1]$$$ and its corresponding $$$c=[6, 5.5, 4.75, 4.875]$$$.
