Robot

Ölkə Olimpiya bu gün bayram edir!

Olimpiya küçəsindəki yeganə poçt şöbəsi hədiyyələrlə doludur və onları mümkün qədər tez bir zamanda ünvanlarına çatdırmaq lazımdır. Bu gün cəmi N hədiyyə gəlib, i-ci hədiyyə h[i] nömrəli evə çatdırılmalıdır. Müxtəlif hədiyyələr eyni evə ünvanlana bilər.

Poçt şöbəsi Olimpiya küçəsinin başlanğıcında yerləşir. Poçtun sağında düz yol boyunca evlər yerləşir və onların nömrələnməsi 1-dən başlayır; i-ci ev poçtdan i kilometr məsafədə yerləşir. Hədiyyələrin çatdırılması üçün eksperimental rejimdə eyni anda ən çox K əşyanı daşıya bilən xüsusi poçt robotu istifadə olunur. Bir hədiyyənin yüklənməsi və boşaldılması bir dəqiqə çəkir, iki hədiyyə eyni anda yüklənə və ya boşaldıla bilməz. Robot bir kilometr məsafəni də bir dəqiqəyə qət edir.

Məsələ

Hər bir hədiyyə haqqında məlumat və robotun xüsusiyyətlərinə əsasən, robotun bütün hədiyyələri ünvanlarına çatdırıb poçt şöbəsinə qayıtması üçün lazım olan ən az vaxtı dəqiqələrlə müəyyən edən proqram yazın. Əvvəlcə bütün hədiyyələr və robot şöbədədir.

Giriş məlumatları

Giriş məlumatlarının ilk sətiri iki tam ədəd N və K (1 ≤ N ≤ 10^5, 1 ≤ K ≤ 10^3) — poçt şöbəsinə gələn hədiyyələrin sayı və robotun eyni anda daşıya biləcəyi maksimum əşyaların sayı. İkinci sətir boşluqla ayrılmış N tam ədəd ehtiva edir: i-ci ədəd h[i] (1 ≤ h[i] ≤ 10^6) — i-ci hədiyyənin çatdırılmalı olduğu evin nömrəsi. Evlərin göstərilən nömrələrlə həqiqətən Olimpiya küçəsində yerləşdiyi təmin edilir.

Çıxış məlumatları

Çıxış məlumatlarının yeganə sətiri bir tam ədəd ehtiva etməlidir — robotun hədiyyələri ünvanlarına çatdırıb poçt şöbəsinə qayıtması üçün lazım olan ən az vaxt dəqiqələrlə.

Nümunələr

Qiymətləndirmə

Test dəsti 4 blokdan ibarətdir və hər biri üçün aşağıdakı şərtlər yerinə yetirilir:

1. 25 % xal: 1 ≤ N ≤ 10, 1 ≤ K ≤ 5, 1 ≤ h[i] ≤ 10^2.

2. 25 % xal: 1 ≤ N ≤ 10^3, 1 ≤ K ≤ 10^2, 1 ≤ h[i] ≤ 10^4.

3. 25 % xal: 1 ≤ N ≤ 10^5, 1 ≤ K ≤ 10^3, 1 ≤ h[i] ≤ 10^4.

4. 25 % xal: 1 ≤ N ≤ 10^5, 1 ≤ K ≤ 10^3, 1 ≤ h[i] ≤ 10^6.

İzah. Hədiyyələri 1-dən 7-yə qədər nömrələyək. Onda çatdırmanın optimal planlarından biri belə görünür:

• 2 dəqiqə: 5 və 6 hədiyyələrin yüklənməsi (hər ikisi 1 nömrəli evə çatdırılmalıdır),

• 1 dəqiqə: robotun şöbədən 1 nömrəli evə hərəkəti,

• 2 dəqiqə: 5 və 6 hədiyyələrin boşaldılması,

• 1 dəqiqə: robotun 1 nömrəli evdən şöbəyə hərəkəti,

• 2 dəqiqə: 2 və 7 hədiyyələrin yüklənməsi (2 hədiyyə 9 nömrəli evə, 7 hədiyyə isə 3 nömrəli evə çatdırılmalıdır),

• 9 dəqiqə: robotun şöbədən 9 nömrəli evə hərəkəti,

• 1 dəqiqə: 2 hədiyyənin boşaldılması,

• 6 dəqiqə: robotun 9 nömrəli evdən 3 nömrəli evə hərəkəti,

• 1 dəqiqə: 7 hədiyyənin boşaldılması,

• 3 dəqiqə: robotun 3 nömrəli evdən şöbəyə hərəkəti,

• 3 dəqiqə: 1, 3 və 4 hədiyyələrin yüklənməsi (1 və 3 hədiyyələr 3 nömrəli evə, 4 hədiyyə isə 2 nömrəli evə çatdırılmalıdır),

• 2 dəqiqə: robotun 2 nömrəli evə hərəkəti,

• 1 dəqiqə: 4 hədiyyənin boşaldılması,

• 1 dəqiqə: robotun 2 nömrəli evdən 3 nömrəli evə hərəkəti,

• 2 dəqiqə: 1 və 3 hədiyyələrin boşaldılması,

• 3 dəqiqə: robotun 3 nömrəli evdən şöbəyə hərəkəti.