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个小时。