该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

三三村有 $n$ 名村民，33DAI 是村长。他拿到了一条重要通知，需要让全村 $n$ 名村民都知道。

33DAI 可以亲自通知村民，每通知一人花费 $p$。

已经知道这条通知的村民也能帮忙转告：对第 $i$ 名村民，只要他知道了通知（无论是 33DAI 亲自通知的，还是别人转告的），他就可以转告至多 $a_i$ 名其他村民，每转告一人花费 $b_i$。

33DAI 想知道：让全部 $n$ 名村民都知道这条通知，最少要花多少钱？

输入格式

从文件 spread.in 读入数据。

输入的第一行是一个整数 $t$，表示测试用例组数。

接下来依次给出 $t$ 组测试用例，每组测试用例的格式为：

• 第一行两个整数 $n, p$，分别表示村民人数与 33DAI 亲自通知一人的花费；
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$；
• 第三行 $n$ 个整数 $b_1, b_2, \dots, b_n$。

输出格式

输出到文件 spread.out。

对每组测试用例输出一行一个整数，表示让全部 $n$ 名村民都知道这条通知所需的最小花费。

3
6 3
2 3 2 1 1 3
4 3 2 6 3 6
1 100000
100000
1
4 94
1 4 2 3
103 96 86 57

16
100000
265

样例 1 解释

第 1 组：33DAI 亲自通知第 $3, 5, 6$ 名村民，花费 $p + p + p = 3 + 3 + 3 = 9$；第 $3$ 名村民转告第 $1, 2$ 名村民，花费 $b_3 + b_3 = 2 + 2 = 4$；第 $2$ 名村民再转告第 $4$ 名村民，花费 $b_2 = 3$。总花费 $9 + 4 + 3 = 16$，此时 $6$ 名村民都知道了通知。

第 2 组只有 $1$ 名村民，因此只能由 33DAI 亲自通知，花费 $p = 100000$，输出 100000。

第 3 组：33DAI 亲自通知第 $4$ 名村民，花费 $p = 94$；第 $4$ 名村民转告第 $1, 2, 3$ 名村民，花费 $b_4 + b_4 + b_4 = 57 + 57 + 57 = 171$。总花费 $94 + 171 = 265$，此时 $4$ 名村民都知道了通知。

样例 2

见 spread2.in 与 spread2.ans。

样例 3

见 spread3.in 与 spread3.ans。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 10^4$；
• $1 \le n \le 10^5$，$1 \le p \le 10^5$；
• $1 \le a_i \le 10^5$，$1 \le b_i \le 10^5$；
• 所有测试用例的 $n$ 之和不超过 $10^5$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。