310729: CF1877B. Helmets in Night Light

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Helmets in Night Lighttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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.

ExampleInput
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
Output
16
100000
265
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.

Output

题目大意:
Pak Chanek 是一个名为 Khuntien 的村庄的首领。在一个灯火通明的夜晚,Pak Chanek 必须通知村里的所有居民一个突发的重要公告。

首先,Pak Chanek 直接向一个或多个居民分享这个公告,每个居民的成本是 p。之后,居民们可以使用一种魔法头盔状的设备将公告分享给其他居民。但是使用这种头盔状设备是有成本的。对于每个 i,如果第 i 个居民至少已经收到一次公告(无论是直接从 Pak Chanek 还是从另一个居民那里),他/她可以以成本 b_i 向最多 a_i 个其他居民分享公告。

如果 Pak Chanek 也可以控制居民们如何将公告分享给其他居民,那么通知 Khuntien 所有 n 个居民关于公告的最小成本是多少?

输入输出数据格式:
输入:
- 第 1 行:一个整数 t(1 ≤ t ≤ 10^4),表示测试用例的数量。
- 每个测试用例的描述:
- 第 1 行:两个整数 n 和 p(1 ≤ n ≤ 10^5;1 ≤ p ≤ 10^5),分别表示居民的数量和 Pak Chanek 直接向一个居民分享公告的成本。
- 第 2 行:n 个整数 a_1, a_2, a_3, ..., a_n(1 ≤ a_i ≤ 10^5),表示每个居民最多可以向多少其他居民分享公告。
- 第 3 行:n 个整数 b_1, b_2, b_3, ..., b_n(1 ≤ b_i ≤ 10^5),表示每个居民向一个其他居民分享公告的成本。
- 保证所有测试用例的 n 之和不超过 10^5。

输出:
- 对于每个测试用例,输出一行,包含一个整数,表示通知所有 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. Pak Chanek 直接向第 3、5、6 个居民分享公告。这需要成本 p+p+p=3+3+3=9。
2. 第 3 个居民向第 1 和第 2 个居民分享公告。这需要成本 b_3+b_3=2+2=4。
3. 第 2 个居民向第 4 个居民分享公告。这需要成本 b_2=3。
总成本是 9+4+3=16。可以证明没有其他成本更低的策略。题目大意: Pak Chanek 是一个名为 Khuntien 的村庄的首领。在一个灯火通明的夜晚,Pak Chanek 必须通知村里的所有居民一个突发的重要公告。 首先,Pak Chanek 直接向一个或多个居民分享这个公告,每个居民的成本是 p。之后,居民们可以使用一种魔法头盔状的设备将公告分享给其他居民。但是使用这种头盔状设备是有成本的。对于每个 i,如果第 i 个居民至少已经收到一次公告(无论是直接从 Pak Chanek 还是从另一个居民那里),他/她可以以成本 b_i 向最多 a_i 个其他居民分享公告。 如果 Pak Chanek 也可以控制居民们如何将公告分享给其他居民,那么通知 Khuntien 所有 n 个居民关于公告的最小成本是多少? 输入输出数据格式: 输入: - 第 1 行:一个整数 t(1 ≤ t ≤ 10^4),表示测试用例的数量。 - 每个测试用例的描述: - 第 1 行:两个整数 n 和 p(1 ≤ n ≤ 10^5;1 ≤ p ≤ 10^5),分别表示居民的数量和 Pak Chanek 直接向一个居民分享公告的成本。 - 第 2 行:n 个整数 a_1, a_2, a_3, ..., a_n(1 ≤ a_i ≤ 10^5),表示每个居民最多可以向多少其他居民分享公告。 - 第 3 行:n 个整数 b_1, b_2, b_3, ..., b_n(1 ≤ b_i ≤ 10^5),表示每个居民向一个其他居民分享公告的成本。 - 保证所有测试用例的 n 之和不超过 10^5。 输出: - 对于每个测试用例,输出一行,包含一个整数,表示通知所有 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. Pak Chanek 直接向第 3、5、6 个居民分享公告。这需要成本 p+p+p=3+3+3=9。 2. 第 3 个居民向第 1 和第 2 个居民分享公告。这需要成本 b_3+b_3=2+2=4。 3. 第 2 个居民向第 4 个居民分享公告。这需要成本 b_2=3。 总成本是 9+4+3=16。可以证明没有其他成本更低的策略。

加入题单

上一题 下一题 算法标签: