Story
My local pizza delivery introduced new discount. You get 50% discount from every second item on your order.
But being greedy capitalists, they forgot to mention that they will rearrange items the way they need to give you as little as possible.
Example
Imagine you ordered
- Pizza $20
- Pizza $20
- Coke $2
- Coke $2
You expect to get $10 discount from the second pizza and $1 from the coke, but they rearrange it as
- Pizza $20
- Coke $2
- Pizza $20
- Coke $2
and give you $2.
Trick
Later I noticed that I can place as many orders as I want simultaneously, so I just split my order into two:
1.
- Pizza $20
- Pizza $20
2.
- Coke $2
- Coke $2
and I got the discount I deserve.
Problem
Can you please help me to write a program that calculate the maximum discount I can get by splitting my order.
It should accept a list of prices and return an amount.
For simplicity, all prices are even numbers, so the result is always an integer. Order is never empty. Input have no specific order.
This is code golf, do all usual rules applies.
Testcases
[10] -> 0
[10,20] -> 5
[10,20,30] -> 10
[2,2,2,2] -> 2
[4,10,6,8,2,40] -> 9
