← 返回题目列表

Codeforces · 439/B

B. Devu,愚蠢的家伙

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

Devu 是个笨蛋,他的学习曲线非常慢。你应该教他n科,第i科有ci章。当你教他的时候,你应该连续地教一个科目的所有章节。

假设他一门学科的初始每章学习能力是 x 小时。换句话说,他可以在 x 小时内学习特定主题的一章。

好吧,Devu 并不完全愚蠢,他也有一个优点。如果您教他一门科目,那么教授下一科目的任何章节所需的时间将比以前所需的时间少 1 小时(请参阅示例以更清楚地理解)。注意他每章的学习力不能少于1小时。

你可以按任何可能的顺序教他 n 个科目。找出 Devu 理解所有科目所需的最短时间(以小时为单位),您将可以自由地做一些有趣的任务,而不是教一个愚蠢的人。

请注意,答案可能不适合 32 位数据类型。

输入

第一行将包含两个空格分隔的整数 n, x (1 ≤ n, x ≤ 105)。下一行将包含 n 个空格分隔的整数:c1, c2, ..., cn (1 ≤ ci ≤ 105)。

输出

输出代表问题答案的单个整数。

示例

输入 #1

2 3
4 1

输出 #1

11

输入 #2

4 2
5 1 2 1

输出 #2

10

输入 #3

3 3
1 1 1

输出 #3

6

注意

看第一个例子。考虑科目的顺序:1、2。当你教 Devu 第一科目时,他每章需要 3 个小时,因此教授第一科目需要 12 个小时。教完第一门课后,他每章的学习时间为2小时。现在教他第二门课需要 2 × 1 = 2 小时。因此您需要花费 12 + 2 = 14 小时。

考虑科目顺序:2, 1。当你教 Devu 第二科目时,那么他每章需要 3 个小时,所以教第二科目需要 3 × 1 = 3 个小时。教完第二课后,他每章的学习时间为2小时。现在教他第一门课需要 2 × 4 = 8 个小时。因此您需要花费 11 个小时。

因此总的来说,这两种情况的最短时间都是 11 小时。

看第三个例子。此示例中的顺序并不重要。当你教 Devu 第一门课时,他每章需要 3 个小时。当你教 Devu 第二门课时,他每章需要 2 个小时。当你教 Devu 第三门课时,他每章需要 1 个小时。总共需要6个小时。