You and friends want to buy flowers. Each flower has some cost . The florist is greedy and wants to maximize his number of new customers, so he increases the sale price of flowers for repeat customers; more precisely, if a customer has already purchased flowers, price for is .
Find and print the minimum cost for your group to purchase flowers.
Note: You can purchase the flowers in any order.
Input Format
The first line contains two integers, (number of flowers to purchase) and (the size of your group of friends, including you).
The second line contains space-separated positive integers describing the cost () for each flower .
Output Format
Print the minimum cost for buying flowers.
Sample Input 0
3 3
2 5 6
Sample Output 0
13
Sample Input 1
3 2
2 5 6
Sample Output 1
15
Explanation
Sample Case 0:
There are flowers and people in your group. Each person buys one flower and the sum of prices paid is dollars, so we print .
Sample Case 1:
There are flowers and people in your group. The first person purchases flowers, and , in order of decreasing price; this means they buy the more expensive flower first at price and the less expensive flower second at price . The second person buys the most expensive flower at price . We print the sum of these purchases (), which is .
C Implementation:
Find and print the minimum cost for your group to purchase flowers.
Note: You can purchase the flowers in any order.
Input Format
The first line contains two integers, (number of flowers to purchase) and (the size of your group of friends, including you).
The second line contains space-separated positive integers describing the cost () for each flower .
Output Format
Print the minimum cost for buying flowers.
Sample Input 0
3 3
2 5 6
Sample Output 0
13
Sample Input 1
3 2
2 5 6
Sample Output 1
15
Explanation
Sample Case 0:
There are flowers and people in your group. Each person buys one flower and the sum of prices paid is dollars, so we print .
Sample Case 1:
There are flowers and people in your group. The first person purchases flowers, and , in order of decreasing price; this means they buy the more expensive flower first at price and the less expensive flower second at price . The second person buys the most expensive flower at price . We print the sum of these purchases (), which is .
C Implementation:
/* Sample program illustrating input/output methods */
#include<stdio.h>
/*int cmpfunc(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}*/
int main(){
//Helpers for input/output
int i, N, K;
int C[102];
scanf("%d %d", &N, &K);
for(i=0; i<N; i++){
scanf("%d", &(C[i]));
}
int result=0;
int x;
int temp;
int j;
//qsort(C,N,sizeof(int),cmpfunc);
for(i=0;i<N-1;i++)
{
for(j=i+1;j<N;j++)
{
if(C[i]<C[j])
{
temp=C[i];
C[i]=C[j];
C[j]=temp;
}
}
}
for(i=0;i<N;i++)
{
x=i/K;
result += (x+1) * C[i];
}
printf("%d\n", result);
}