C. 饺子
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

gsh 非常喜欢吃饺子！每天，他都会前往学苑食堂品尝美味的饺子。食堂每天会供应不同种类和数量的饺子，而 gsh 希望在自己有限的胃容量内，通过合理选择，收获最大的总愉悦值。

食堂今天提供 $$$n$$$ 种不同的饺子，gsh 最多能吃 $$$m$$$ 个饺子。对于食堂提供的饺子，第 $$$i$$$ 种饺子的总数量为 $$$s_i$$$，其基础愉悦值和边际递减系数分别为 $$$a_i$$$ 与 $$$b_i$$$。特别地，在首次品尝该种饺子时，会有一个 $$$c_i$$$ 的"初见惊喜"加成。

具体来说，吃掉的第 $$$i$$$ 种饺子中的第 $$$j$$$ 个，能获得的愉悦值为 $$$e_{i,j}$$$。这个值是预先确定的，与食用的先后顺序无关，计算方式如下： $$$$$$ e_{i,j} = \begin{cases} a_i + c_i, & \text{当 } j=1 \text{ 时（即第一次吃第 } i \text{ 种饺子）} \\ a_i - b_i \times (j - 1), & \text{当 } j \gt 1 \text{ 时} \end{cases} $$$$$$

此外，gsh 的食量有一个"完美区间"。如果他吃的饺子总数恰好在 $$$[l, r]$$$ 的范围内（包含 $$$l$$$ 和 $$$r$$$），他会感到心满意足，从而额外获得 $$$\mathrm{val}$$$ 点的总愉悦值。

请你帮助 gsh 设计一个吃饺子的方案（即决定每种饺子吃几个），使得他获得的总愉悦值最大化。

Input

第一行输入一个整数 $$$T$$$，表示数据组数（$$$1 \le T \le 10^5$$$）。

接下来对每组数据输入如下：

  • 第一行输入 $$$5$$$ 个整数 $$$n,m,\mathrm{val},l,r(1 \le n \le 10^5,\sum n \le 3 \times 10^5,0 \le m, \mathrm{val} \le 10^6,0 \le l \le r \le m)$$$。
  • 接下来 $$$n$$$ 行，第 $$$i$$$ 行输入 $$$4$$$ 个整数 $$$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$$$）。

注意：本题不存在对 $$$\sum m$$$ 的约束条件。

Output

对每组数据，输出一行一个整数，表示最大愉悦值。

Example
Input
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
48
50
742
Note

对于第一组数据，只有一种饺子。

gsh 吃了 $$$3$$$ 个饺子，获得的愉悦值分别是：$$$29,11,3$$$，同时额外获得 $$$5$$$ 点愉悦值（由于饺子总数满足 $$$l\le 3\le r$$$）。

对于第二组数据，有 $$$3$$$ 种饺子。

gsh 吃了 $$$8$$$ 个第一种饺子，$$$8$$$ 个第二种饺子，$$$2$$$ 个第三种饺子，获得的愉悦值是 $$$50$$$（包含额外获得的 $$$40$$$ 点愉悦值）。