题目描述

修仙世界中，铧天帝道法无数，常念道：”我为天帝，当镇压世间一切敌！“ 同为”大帝之姿“的海神前来挑战，两位大能打到大道都要磨灭了，铧天帝将要饮恨之时，春秋蝉恰好出世，铧天帝一把抓住，顷刻炼化！”这竟是光阴长河？且待我回归，必将复仇血恨！“

在光阴之河中前行需要仙力，开始时，铧天帝没有仙力，在光阴长河中有 $n$ 个节点，每个节点之间的距离为 $v_i$ ，每个节点都能恢复仙力，恢复 $1$ 度仙力需要 $a_i$ 的时间，且 $1$ 度仙力能支撑铧天帝走 $d$ 的单位长度。

问：铧天帝从第 $1$ 个节点走到第 $n$ 个节点，至少需要花费多少时间。

输入格式

第一行一个正整数 $T$（$1\le T \le 100$），代表测试样例的组数。

每个测试样例共有 $3$ 行。

第一行包含两个正整数 $n$ （ $1 \le n \le10^5$ ）和 $d$ （$1 \le d \le 10^5$），分别表示光阴河上节点的数量和 $1$ 度仙力可以前进的距离。

第二行包含 $n - 1$ 个正整数 $v_1, v_2\dots v_{n-1}$（ $1 \le v_i \le10^5$ ）分别表示节点间的距离。

第三行包含 $n$ 个正整数 $a_1, a_2 \dots a_n$（ $1 \le a_i \le10^5$ ）分别表示在不同节点恢复仙力的时间。

数据保证 $\sum n \le 10^5$。

输出格式

输出 $T$ 行，每行仅包含一个正整数，表示从节点 $1$ 走到节点 $n$，铧天帝至少要花多少时间。

输入样例

1
5 4
10 10 10 10
9 8 9 6 5

输出样例

79

提示

对于样例 $1$：最优方案下，铧天帝在节点 $1$ 恢复了 $3$ 度仙力，在节点 $2$ 恢复了 $5$ 度仙力，在节点 $4$ 恢复了 $2$ 度仙力 。