← 返回题目列表

Codeforces · 994/B

B. 多边形表的骑士

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

与圆桌骑士不同,多边形桌骑士被剥夺了贵族身份,乐于互相残杀。但每个骑士都有一定的力量,当且仅当他的力量大于受害者的力量时,一个骑士才能杀死另一个骑士。然而,即使这样的骑士也会折磨他的良心,所以他最多只能杀死$$$k$$$其他骑士。此外,每个骑士都有一定数量的硬币。击杀后,骑士可以拾取所有受害者的硬币。

现在每个骑士都会思考:如果他杀死其他骑士,他能拥有多少金币?

你应该为每个骑士回答这个问题。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(1 \le n \le 10^5, 0 \le k \le \min(n-1,10))$$$ — 语句中的骑士数量和数量 $$$k$$$。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2 ,\ldots,p_n$$$ $$$(1 \le p_i \le 10^9)$$$ — 骑士的力量。所有 $$$p_i$$$ 都是不同的。

第三行包含 $$$n$$$ 整数 $$$c_1, c_2 ,\ldots,c_n$$$ $$$(0 \le c_i \le 10^9)$$$ — 每个骑士拥有的硬币数量。

输出

打印 $$$n$$$ 整数 - 每个骑士只有杀死其他骑士才能拥有的最大硬币数量。

示例

输入 #1

4 2
4 5 9 7
1 2 11 33

输出 #1

1 3 46 36

输入 #2

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

输出 #2

1 3 5 7 9

输入 #3

1 0
2
3

输出 #3

3

注意

考虑第一个例子。

- 第一个骑士是最弱的,所以他不能杀死任何人。这让他只剩下最初拥有的唯一硬币。
- 第二个骑士可以杀死第一个骑士并将他的硬币添加到他自己的两个骑士中。
- 第三个骑士是最强的,但他不能杀死超过 $$$k = 2$$$ 的其他骑士。杀死第二个和第四个骑士是最佳选择:$$$2+11+33 = 46$$$。
- 第四个骑士应该杀死第一个和第二个骑士:$$$33+1+2 = 36$$$。

在第二个例子中,第一个骑士不能杀死任何人,而其他所有骑士都应该杀死索引比自己小一的人。

在第三个例子中只有一名骑士,所以他不能杀死任何人。