← 返回题目列表

AtCoder · awc0086_b

B. 不连续重复的训练

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

分数: 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