考虑一条无限长的坐标轴。在坐标 $1, 2, \dots, n$ 处各有一朵花。坐标 $i$ 处的花具有吸引力 $a_i$。

两名玩家正在进行一场游戏。第一名玩家从坐标 $1$ 开始。游戏过程如下：

1. 第一名玩家当前位于坐标 $i$，他选择一个从 $\ell_i$ 到 $r_i$ 的整数距离，并向右移动该距离。
2. 如果第一名玩家的坐标超过了 $n$，则游戏结束。
3. 否则，第二名玩家将第一名玩家向左移动 $0$ 到 $c$ 之间的任意距离。但是，此移动不能使第一名玩家到达坐标 $i+1$ 的左侧。
4. 第一名玩家拿走他当前所在位置的花，游戏回到第 1 步。

第一名玩家希望最大化他所拿到的花的吸引力总和，而第二名玩家希望最小化该总和。

你的任务是计算如果两名玩家都采取最优策略，第一名玩家最终获得的吸引力总和。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 3 \cdot 10^5$)，表示测试用例的数量。接下来是各测试用例。

每个测试用例的第一行包含两个整数：花的数量 $n$ ($1 \le n \le 3 \cdot 10^5$) 和限制 $c$ ($0 \le c \le n$)。接下来的三行，每行包含 $n$ 个整数，依次描述数组 $\ell$、$r$ 和 $a$ ($1 \le \ell_i \le r_i \le n$; $-10^9 \le a_i \le 10^9$)。注意吸引力可能是负数。

所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数：如果两名玩家都采取最优策略，第一名玩家最终获得的吸引力总和。

样例

样例输入 1

2
6 2
1 1 2 2 1 1
2 1 3 2 1 1
2 3 1 -1 -1 1
4 4
1 1 1 1
2 2 1 1
-1 -3 -2 -4

样例输出 1

3
-9