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