Description

魔法师 Mike 面前有 $n$ 座雪山，从左到右依次编号为 $1$ 到 $n$， 初始时第 $i$ 座雪山的高度为 $h_i$。这时气候即将变暖，气候变暖后，每分钟每座雪山的高度都会减 $1$，如果雪山高度为 $0$ 了就不会继续减 $1$。

Mike 想让这 $n$ 座雪山的高度序列变为单调不递增的，即变换后的序列满足 $h^{'}_i \ge h^{'}_{i+1}(1 \le i<n)$。

Mike 可以就等气候变暖让雪山高度不断减 $1$ 来达到他的目的，但是每分钟 Mike 会丧失 $c$ 魔力值。就这么等着不仅耗时还耗魔力，Mike 可以在气候变暖前一刻瞬间进行若干次（可以是 $0$ 次）操作，每次操作 Mike 可以选择第 $i$ 座雪山，让它的高度加 $1$，代价是消耗 $a_i$ 单位的魔力值。相同的雪山可以被操作若干次。若干次操作结束后气候立马变暖，雪山高度每分钟减 $1$。

Mike 想知道达到他的目的所需要消耗的最小魔力值。请你帮帮他，只需要告诉他答案即可。

Input

第一行一个整数 $T\ (1 \le T \le 10^5)$，表示数据组数。

对于每组数据：

第一行输入两个整数 $n\ (1 \le n \le 5 \cdot 10^5)$ 和 $c\ (1\le c \le 10^9)$。

第二行输入 $n$ 个整数 $h_i\ (1 \le h_i \le 10^8)$。

第三行输入 $n$ 个整数 $a_i\ (1 \le a_i \le 10^4)$。

对于全部数据，保证 $\sum{n} \le 5 \cdot 10^5$。

Output

输出 $T$ 行，每行一个整数表示第 $i$ 组数据的答案。

Samples

3
4 3
1 3 1 4
5 2 1 1
6 4
1 1 4 5 1 4
1 9 1 9 1 1
7 1
7 2 6 3 5 1 4
1 1 1 1 1 1 1

12
20
6

Resources

电子科技大学第十五届 ACM 趣味程序设计竞赛