← 返回题目列表

AtCoder · yahoo_procon2017_qual_b

B. 拍卖

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

配点 : 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