B - 連続禁止のトレーニング 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君はジムでトレーニングを行います。このジムには N 種類のトレーニングマシンがあり、i 番目のマシンを 1 回使うと A_i の運動効果を得られます。この運動効果はマシンごとに固定されており、同じマシンを使うたびに同じ値が加算されます。

高橋君はちょうど K 回マシンを使う予定です。各回では N 種類のマシンの中から 1 つを選んで使いますが、直前に使ったマシンと同じものを続けて選ぶことはできません。この条件さえ満たせば、過去に使ったことのあるマシンを再び選ぶことは自由にできます。また、1 回目はどのマシンから始めても構いません。

高橋君が 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
  • 1 行目には、マシンの種類数を表す整数 N と、マシンを使う回数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各マシンを 1 回使うことで得られる運動効果を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

高橋君が得られる運動効果の合計の最大値を 1 行で出力してください。

入力例 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

Score : 300 pts

Problem Statement

Takahashi will train at a gym. The gym has N types of training machines, and using the i-th machine once provides an exercise effect of A_i. This exercise effect is fixed for each machine, and the same value is added each time the same machine is used.

Takahashi plans to use machines exactly K times. Each time, he chooses one of the N types of machines to use, but he cannot choose the same machine that was used immediately before. As long as this condition is satisfied, he is free to choose a machine that has been used in the past. Also, he may start with any machine on the first use.

Find the maximum total exercise effect that Takahashi can obtain from K training sessions.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N K
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of types of machines and an integer K representing the number of times machines are used, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the exercise effect obtained by using each machine once, separated by spaces.

Output

Print the maximum total exercise effect that Takahashi can obtain, in one line.

Sample Input 1

3 4
5 3 2

Sample Output 1

16

Sample Input 2

4 7
10 8 6 4

Sample Output 2

64

Sample Input 3

5 1000000000
1000000000 999999999 500000000 100 1

Sample Output 3

999999999500000000