Robot#7665
In the country of Olympia, today is a holiday!
The only post office on Olympic Street is bustling with gifts that need to be delivered to their recipients as quickly as possible. Today, gifts have arrived, and the -th gift is destined for the house numbered h_i. Multiple gifts may be addressed to the same house.
The post office is situated at the start of Olympic Street. To the right, along a straight road, are houses numbered starting from ; the -th house is located kilometers from the post office. For delivery, a special postal robot is used in an experimental mode, capable of carrying up to items at once. Loading or unloading a single gift takes one minute, and two gifts cannot be loaded or unloaded simultaneously. The robot travels one kilometer in one minute.
Write a program that, based on the details of each gift and the robot's capabilities, calculates the minimum time in minutes for the robot to deliver all the gifts to their recipients and return to the post office. Initially, all gifts and the robot are at the post office.
The first line of input contains two integers and (1 \le N \le 10^5, 1 \le K \le 10^3) — the number of gifts at the post office and the maximum number of items the robot can carry at once. The second line contains integers separated by spaces: the -th number is h_i (1 \le h_i \le 10^6) — the house number to which the -th gift needs to be delivered. It is guaranteed that houses with these numbers are located on Olympic Street.
The output should be a single integer — the minimum time in minutes for the robot to deliver all the gifts and return to the post office.
Example 1
Let's number the gifts from 1 to 7. An optimal delivery plan might look like this:
- 2 minutes: loading gifts 5 and 6 (both for house 1), - 1 minute: traveling from the post office to house 1, - 2 minutes: unloading gifts 5 and 6, - 1 minute: returning from house 1 to the post office, - 2 minutes: loading gifts 2 and 7 (gift 2 for house 9, gift 7 for house 3), - 9 minutes: traveling from the post office to house 9, - 1 minute: unloading gift 2, - 6 minutes: traveling from house 9 to house 3, - 1 minute: unloading gift 7, - 3 minutes: returning from house 3 to the post office, - 3 minutes: loading gifts 1, 3, and 4 (gifts 1 and 3 for house 3, gift 4 for house 2), - 2 minutes: traveling to house 2, - 1 minute: unloading gift 4, - 1 minute: traveling from house 2 to house 3, - 2 minutes: unloading gifts 1 and 3, - 3 minutes: returning from house 3 to the post office.
The test set consists of 4 blocks, each with the following conditions:
1. 25% of points: 1 \le N \le 10, 1 \le K \le 5, 1 \le h_i \le 10^2.
2. 25% of points: 1 \le N \le 10^3, 1 \le K \le 10^2, 1 \le h_i \le 10^4.
3. 25% of points: 1 \le N \le 10^5, 1 \le K \le 10^3, 1 \le h_i \le 10^4.
4. 25% of points: 1 \le N \le 10^5, 1 \le K \le 10^3, 1 \le h_i \le 10^6.