Problem Description
You are still an inter-galactic traveller in a 1-dimensional space. Sadly, there are no wormholes to help you now. However, on your last trip, you have acquired s number of dark matter spheres.
These dark matter spheres are special objects, they allow you to travel twice as fast. This indicates that the time required for any trip will be halved.
Possessing such dark matter spheres, you want to minimize the time of your future trips so that you spend the least amount of time travelling in space.
Each future trip is actually a round-trip, meaning that for the ith trip, you take ti years to reach your destination, and then ti years to return. Using a sphere will increase your speed for the entire trip, making the duration required much shorter.
You can only use one sphere of dark matter for each trip.
Input
The first line of input consists of 2 integers, n and s. n is the number of future trips you are going to engage in. s is the number of dark matter spheres you possess.
The following lines of input will consist of n space-separated numbers, with the ith number being ti.
n and s will be not more than 1000 and the amount of time required for each trip will be not more than 1000 as well.
Output
Output the shortest amount of time you need to travel in space yet still accomplishing all the trips, in years.
Sample Input
5 3
5 8 9 1 3
Sample Output
30
Explanation for Output
Without using any spheres, the total time required will be 5*2 + 8*2 + 9*2 + 1*2 + 3*2 = 52
Using 3 spheres, the lowest amount of time required will be 2.5*2 + 4*2 + 4.5*2 + 1*2 + 3*2 = 30