分数: 300 分
问题陈述
高桥将在健身房训练。健身房有 N 训练机器的类型以及使用 i第机器一次提供的锻炼效果为 A_i。这个锻炼效果对于每台机器都是固定的,每次使用同一台机器都会增加相同的值。
高桥计划使用机器 K 次。每次他都会选择其中之一 N 使用的机器类型,但是 他无法选择之前使用过的同一台机器。只要满足这个条件,他就可以自由选择过去使用过的机器。此外,他可以在第一次使用任何机器时开始。
求高桥可以获得的最大总运动效果 K 培训课程。
约束
- 2 \leq N \leq 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N K A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 表示机器类型的数量和一个整数 K 代表机器的使用次数,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每台机器使用一次获得的锻炼效果,以空格分隔。
输出
在一行中打印高桥可以获得的最大总锻炼效果。
示例输入 1
3 4 5 3 2
示例输出 1
16
示例输入 2
4 7 10 8 6 4
示例输出 2
64
示例输入 3
5 1000000000 1000000000 999999999 500000000 100 1
示例输出 3
999999999500000000