← 返回题目列表

Codeforces · 1394/A

A. 波博尼乌与杜聊天

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

您用过QQ聊天软件吗?嗯,在QQ聊天群里,管理员可以封住一个用户好几天。

在波波尼的聊天群里,有一个叫杜毅的人,每天都喜欢调侃波波尼。

小杜将在群里聊天 $$$n$$$ 天。在第 $$$i$$$ 天:

- 如果杜会说话,他会用有趣的因素$$$a_i$$$来取笑博博尼乌。但在那之后,他可能会被封口,这取决于博博尼乌的心情。
- 否则,杜不会做任何事情。

Boboniu 的心情是恒定的 $$$m$$$。在第 $$$i$$$ 天:

- 如果 Du 能说话并且 $$$a_i>m$$$,那么 Boboniu 会生气并把他堵住 $$$d$$$ 天,这意味着 Du 在第 $$$i+1, i+2, \cdots, \min(i+d,n)$$$ 天不能说话。
- 否则,波博尼乌不会做任何事情。

总的乐趣因子是杜能说话的日子里的乐趣因子的总和。

Du 要求你在 $$$a$$$ 的所有可能排列中找到最大的总乐趣因子。

输入

第一行包含三个整数 $$$n$$$、$$$d$$$ 和 $$$m$$$ ($$$1\le d\le n\le 10^5,0\le m\le 10^9$$$)。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots,a_n$$$ ($$$0\le a_i\le 10^9$$$)。

输出

打印一个整数:$$$a$$$的所有排列中最大的总乐趣因子。

示例

输入 #1

5 2 11
8 10 15 23 5

输出 #1

48

输入 #2

20 2 16
20 5 8 2 18 16 2 16 16 1 5 16 2 13 6 16 4 17 21 7

输出 #2

195

注意

在第一个示例中,您可以设置$$$a'=[15, 5, 8, 10, 23]$$$。那么杜的聊天记录将是:

1. 用有趣的因素 $$$15$$$ 取笑 Boboniu。
2. 保持沉默。
3. 保持沉默。
4. 用有趣的因素 $$$10$$$ 取笑 Boboniu。
5. 用有趣的因素 $$$23$$$ 取笑 Boboniu。

因此总的乐趣系数是 $$$48$$$。