gsh loves dumplings! Every day, he visits the school cafeteria to enjoy delicious dumplings. The cafeteria provides different types and quantities of dumplings each day, and gsh hopes to maximize his total pleasure value within his limited stomach capacity through reasonable choices.

The cafeteria provides $n$ different types of dumplings today, and gsh can eat at most $m$ dumplings. For the dumplings provided by the cafeteria, the total quantity of the $i$-th type is $s_i$, and its base pleasure value and marginal diminishing coefficient are $a_i$ and $b_i$, respectively. Specifically, when tasting a type of dumpling for the first time, there is an additional "first-time surprise" bonus of $c_i$.

Specifically, the pleasure value obtained from eating the $j$-th dumpling of the $i$-th type is $e_{i,j}$. This value is predetermined and independent of the order of consumption, calculated as follows:

$$e_{i,j} = \begin{cases} a_i + c_i, & \text{if } j = 1 \text{ (i.e., the first time eating the } i\text{-th type)} \\ a_i - b_i \times (j - 1), & \text{if } j > 1 \end{cases}$$

In addition, gsh's appetite has a "perfect range." If the total number of dumplings he eats is exactly in the range $[l, r]$ (inclusive of $l$ and $r$), he will feel satisfied and receive an additional $val$ points of total pleasure value.

Please help gsh design a dumpling-eating plan (i.e., decide how many of each type of dumpling to eat) to maximize his total pleasure value.

Input

The first line contains an integer $T$, representing the number of test cases ($1 \le T \le 10^5$).

For each test case: The first line contains 5 integers $n, m, val, l, r$ ($1 \le n \le 10^5, \sum n \le 3 \times 10^5, 0 \le m, val \le 10^6, 0 \le l \le r \le m$). The next $n$ lines each contain 4 integers $s_i, a_i, b_i, c_i$ ($1 \le s_i, b_i \le 10^6, -10^6 \le a_i \le 10^6, 0 \le c_i \le 10^6$).

Note: There is no constraint on $m$ in this problem.

Output

For each test case, output a single integer representing the maximum total pleasure value.

Examples

Input 1

3
1 14 5 1 4
19 19 8 10
3 25 40 18 20
20 4 1 4
20 3 1 6
10 -1 2 4
3 25 40 18 20
20 40 3 40
20 30 1 60
10 -10 2 55

Output 1

48
50
742

Note

For the first test case, there is only one type of dumpling. gsh eats 3 dumplings, and the pleasure values obtained are: 29, 11, 3. He also receives an additional 5 points of pleasure value (because the total number of dumplings satisfies $l \le 3 \le r$).

For the second test case, there are 3 types of dumplings. gsh eats 8 of the first type, 8 of the second type, and 2 of the third type, obtaining a total pleasure value of 50 (including the additional 40 points of pleasure value).