「みんなのプロコン」

B - オークション


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 200

問題文

高橋君はオークションサイトでの買い物を楽しんでいます。 今、このオークションサイトには N 個の商品が出品されており、i 個目の商品の値段は A_i 円です。 このオークションサイトでは、一日に一個までしか商品を買うことができず、 一日たつごとにどの商品も値段が 1 円ずつ増えます。 もちろん、同じ商品は一度までしか買うことはできません。

高橋君は K 個の商品を買いたいです。 高橋君が K 個の商品を買うために必要な金額の最小値を求めてください。

制約

  • 1 ≦ N ≦ 10^5
  • 1 ≦ K ≦ N
  • 1 ≦ A_i ≦ 10^9

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 ... A_N

出力

高橋君が K 個の商品を買うためにかかる金額の総和の最小値を一行に出力せよ。


入力例 1

3 2
1 3 5

出力例 1

5

例えば、以下のように買い物をすれば高橋君は 5 円で 2 個の商品を買うことができます。

  • 1 日目に 3 円の商品を買う。このとき、残りの商品の値段は 1 円ずつ上がり、2 円と 6 円の商品が残る。
  • 2 日目に 2 円の商品を買う。このとき、使った金額の合計は 5 円となる。

入力例 2

5 3
6 3 2 4 7

出力例 2

12

Submit提出する