Convoy

You and your friends have gathered at your house to prepare for the Big Game, which you all plan to attend in the afternoon at the football stadium across town. The problem: you only have $k$ cars between you, with each car seating five people (including the driver), so you might have to take multiple trips to get all $n$ people to the stadium. In addition, some of your friends know the city better than others, and so take different amounts of time to drive to the stadium from your house. You’d like to procrastinate as long as possible before hitting the road: can you concoct a transportation plan that gets all people to the stadium in the shortest amount of time possible?

More specifically, each person $i$ currently at your house can drive
to the stadium in $t_ i$
minutes. All $k$ cars are
currently parked at your house. Any person can drive any car
(so the cars are interchangeable). After a car arrives at the
stadium, any person currently at the stadium can immediately
start driving back to your house (and it takes person
$i$ the same amount of
time $t_ i$ to drive back
as to drive to the stadium), or alternatively, cars can be
temporarily or permanently parked at the stadium. Drivers
driving to the stadium can take up to four passengers with
them, but drivers driving back can *NOT* take any
passenger. You care only about getting all $n$ people from your house to the
stadium—you do *NOT* need to park all $k$ cars at the stadium, if doing so
would require more time than an alternative plan that leaves
some cars at your house.

The first line of input contains two space-separated integers $n$ and $k$ $(1 \leq n,k \leq 20\, 000)$, the number of people at your house and the number of available cars. Then follow $n$ lines containing a single integer each; the $i$th such integer is the number of seconds $t_ i$ $(1 \leq t_ i \leq 1\, 000\, 000)$ that it takes person $i$ to drive from your house to the stadium, or vice-versa.

Print the minimum number of seconds it takes to move all $n$ people from your house to the stadium, if all people coordinate and drive optimally.

Sample Input 1 | Sample Output 1 |
---|---|

11 2 12000 9000 4500 10000 12000 11000 12000 18000 10000 9000 12000 |
13500 |

Sample Input 2 | Sample Output 2 |
---|---|

6 2 1000 2000 3000 4000 5000 6000 |
2000 |