Helmets in Night Light
Contest: Codeforces Round 902 (Div. 1, based on COMPFEST 15 - Final Round)
Difficulty rating: 1000
Tags: greedy, sortings

Pak Chanek is the chief of a village named Khuntien. On one night filled with lights, Pak Chanek has a sudden and important announcement that needs to be notified to all of the $$$n$$$ residents in Khuntien.

First, Pak Chanek shares the announcement directly to one or more residents with a cost of $$$p$$$ for each person. After that, the residents can share the announcement to other residents using a magical helmet-shaped device. However, there is a cost for using the helmet-shaped device. For each $$$i$$$, if the $$$i$$$-th resident has got the announcement at least once (either directly from Pak Chanek or from another resident), he/she can share the announcement to at most $$$a_i$$$ other residents with a cost of $$$b_i$$$ for each share.

If Pak Chanek can also control how the residents share the announcement to other residents, what is the minimum cost for Pak Chanek to notify all $$$n$$$ residents of Khuntien about the announcement?

Input format:
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 format:
For each test case, output a line containing an integer representing the minimum cost to notify all $$$n$$$ residents of Khuntien about the announcement.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
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

Example output:
16
100000
265

Editorial:
Notice that since there are $$$n$$$ residents, there must be $$$n$$$ shares.
There are two types of shares. A share directly by Pak Chanek to a resident, and a share by a resident to another resident. A share by Pak Chanek is unlimited, while a share by a resident is limited by $$$a_i$$$. So there are unlimited shares with cost $$$p$$$ and for each $$$i$$$, there are $$$a_i$$$ shares with cost $$$b_i$$$.
In the beginning, no residents are notified about the announcement, so Pak Chanek must share once to some resident in the beginning.
After that, since there are $$$n-1$$$ residents remaining, there must be $$$n-1$$$ shares. Theoretically, the lowerbound of the minimum cost is the $$$n-1$$$ cheapest shares (including Pak Chanek's shares). Turns out, there is always a strategy to use the $$$n-1$$$ cheapest shares to notify all $$$n$$$ residents after the first share by Pak Chanek.
The strategy is we share the announcement to the residents with the smallest values of $$$b_i$$$ first. Using the fact that $$$a_i\geq1$$$, we can deduce that we will always have a resident with an available share.
We can solve this using a simple sorting or a priority queue. Keep in mind about the unlimited shares with cost $$$p$$$.
Time complexity for each test case: $$$O(n\log n)$$$