Description

deepl翻译

Pak Chanek 是一个名叫坤甸（Khuntien）的村庄的村长。在一个灯火通明的夜晚，Pak Chanek 突然接到一个重要通知，需要通知坤甸的所有 $n$ 居民。

首先，Pak Chanek 会先直接发给一个或多个村民，通知一个村民产生 $p$ 的代价 。之后，居民可以使用一个神奇的头盔状装置将公告分享给其他居民。不过，使用头盔形装置需要付费。在每 $i$ 个居民中，如果 $i$ -居民至少得到过一次公告（头盔给的和村长给的都行），那么他/她最多可以将公告分享给 $a_i$ 个其他居民，每次分享的费用为 $b_i$ 。

如果 Pak Chanek 也可以控制居民向其他居民分享公告的方式，那么 Pak Chanek 通知坤甸所有 $n$ 居民该公告的最低成本是多少？

Input

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The following lines contain the description of each test case.

The first line contains two integers $n$ and $p$ ($1 \leq n \leq 10^5$; $1 \leq p \leq 10^5$) — the number of residents and the cost for Pak Chanek to share the announcement directly to one resident.

The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1\leq a_i\leq10^5$) — the maximum number of residents that each resident can share the announcement to.

The third line contains $n$ integers $b_1,b_2,b_3,\ldots,b_n$ ($1\leq b_i\leq10^5$) — the cost for each resident to share the announcement to one other resident.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a line containing an integer representing the minimum cost to notify all $n$ residents of Khuntien about the announcement.

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

2
5 4
2 2 3 1 1
1 1 3 3 2
5 4
2 3 1 3 3
3 2 2 2 1

8
9

Note

In the first test case, the following is a possible optimal strategy:

1. Pak Chanek shares the announcement directly to the $3$-rd, $5$-th, and $6$-th resident. This requires a cost of $p+p+p=3+3+3=9$.
2. The $3$-rd resident shares the announcement to the $1$-st and $2$-nd resident. This requires a cost of $b_3+b_3=2+2=4$.
3. The $2$-nd resident shares the announcement to the $4$-th resident. This requires a cost of $b_2=3$.

The total cost is $9+4+3=16$. It can be shown that there is no other strategy with a smaller cost.

deepl 翻译

注

在第一个测试案例中，以下是一个可能的最优策略：

1. Pak Chanek 直接向 $3$ -rd、 $5$ -th 和 $6$ -th 居民分享公告。这需要花费 $p+p+p=3+3+3=9$ 。
2. $3$ -rd居民与 $1$ -st和 $2$ -nd居民共享公告。这需要花费 $b_3+b_3=2+2=4$ 。
3. $2$ nd居民向 $4$ /th居民分享公告。这需要花费 $b_2=3$ 。

总成本为 $9+4+3=16$ 。可以证明，没有其他策略的成本更低。