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$$$。可以证明,没有其他策略的成本更小。