← 返回题目列表

Codeforces · 1876/A

A. 夜灯头盔

中文机器翻译题面 查看原题

Pak Chanek 是一个名叫 Khuntien 的村庄的村长。在一个灯火通明的夜晚,Pak Chanek 突然发布了一项重要公告,需要通知昆田所有 $$$n$$$ 居民。

首先,Pak Chanek 直接向一位或多位居民分享该公告,每人费用为 $$$p$$$。之后,居民可以使用神奇的头盔状装置将公告分享给其他居民。然而,使用头盔状装置是有成本的。对于每 $$$i$$$,如果第 $$$i$$$ 居民至少收到一次公告(直接从 Pak Chanek 或其他居民处),他/她可以将公告分享给至多 $$$a_i$$$ 其他居民,每股费用为 $$$b_i$$$。

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

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。以下行包含每个测试用例的描述。

第一行包含两个整数 $$$n$$$ 和 $$$p$$$ ($$$1 \leq n \leq 10^5$$$; $$$1 \leq p \leq 10^5$$$) — 居民数量以及 Pak Chanek 直接向一名居民分享公告的成本。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1\leq a_i\leq10^5$$$) — 每个居民可以共享公告的最大居民数量。

第三行包含 $$$n$$$ 整数 $$$b_1,b_2,b_3,\ldots,b_n$$$ ($$$1\leq b_i\leq10^5$$$) — 每个居民向另一位居民分享公告的成本。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一行,其中包含一个整数,表示通知 Khuntien 所有 $$$n$$$ 居民有关该公告的最低成本。

示例

输入 #1

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

输出 #1

16
100000
265

注意

在第一个测试用例中,以下是可能的最佳策略:

1. Pak Chanek 直接向第 $$$3$$$ 号、第 $$$5$$$ 号和第 $$$6$$$ 号居民分享该公告。这需要$$$p+p+p=3+3+3=9$$$的成本。
2. 第 $$$3$$$-rd 居民将公告分享给第 $$$1$$$-st 和 $$$2$$$-nd 居民。这需要$$$b_3+b_3=2+2=4$$$的成本。
3. 第 $$$2$$$ 位居民将公告分享给第 $$$4$$$ 位居民。这需要$$$b_2=3$$$的成本。

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