Its Confession day in College and the only rule is, One confession per box of chocolates. That is, to make one confession one box of chocolates is required (only to be bought from the stall set up in college), with a note attached to it. There are a variety of chocolate boxes available with different costs. A group of boys decided to make confessions so they want to buy boxes of chocolates.But some boys are conflicted so they decide to make multiple confessions. The shopkeeper wants to maximize his number of new customers and the money he makes. To do this, he decides he'll multiply the price of each box by the number of that customer's previously purchased box plus 1. The first box will be original price (0+1)* original cost, the next will be (1+1) *original cost and so on.

Given the size of the group of friends, the number of boxes they want to purchase and the original prices of the boxes, determine the minimum cost to purchase all of the boxes. How costly can their confessions really be?

For example, if there are k=3 boys that want to buy n=4 boxes that cost c= [1,2,3,4] each will buy one of the boxes priced [2,3,4] at the original price. Having each purchased x=1 box, the first box in the list,c[0] , will now cost (current purchase × previous purchase)* c[0] = (1+1)*1 =2 . The total cost will be 2+3+4+2 =11.

Function should return the minimum cost to purchase all of the boxes.

Parameters:

c: an array of integers representing the original price of each box

k: an integer, the number of boys

Input Format

The first line contains two space-separated integers n and k, the number of boxes and the number of boys.

The second line contains space-separated positive integers c[i], the original price of each box of chocolates.

Constraints:

1<=n,k<=100

1 <= c[i] <=10^ 6

Output: minimum cost to buy all boxes.

EXAMPLE 1:

Sample Input

3 3

2 5 6

Sample Output

13

Explanation

There are n=3 boxes with costs c=[2,5,6] and k=3 people in the group. If each person buys one box, the total cost of prices paid is 2+5+6= 13 dollars. Thus, we print 13 as our answer.

EXAMPLE 2:

Sample Input

3 2

2 5 6

Sample Output

15

Explanation

There are n= 3 boxes with costs c=[2,5,6] and k=2 boys in the group.

The first boy purchases 2 boxes in order of decreasing price; this means they buy the more expensive box (c1= 5) first at price p1 = (0+1) *5 = 5 dollars and the less expensive box (c2= 2) second at price p0 = (1+1)*2 = 4 dollars.

The second person buys the most expensive box (c3=6) at price p2=(0+1)*6 = 6 dollars.

We then print the sum of these purchases, which is 5+4+6= 15, as our answer.

testcaselink

About scoring and submission

**Kunal Desai :** 7715051136**Neelraj Patil :** 9930671144

Privacy Policy