Suvenirlər olan qutular
Açılış mərasiminin son mərhələsi IOI 2015-in keçirildiyi məkanda baş verir. Bu mərhələdə hər bir komanda olimpiadanın təşkilatçı ölkəsindən bir suvenir qutusu almalıdır. Lakin könüllülər mərasimə o qədər aludə olublar ki, suvenirləri tamamilə unudublar. Suvenirləri unutmayan yeganə şəxs Aman idi. O, böyük bir həvəskardır və IOI komandalarının hamısının suvenirlər almasını istəyir, eyni zamanda bütün suvenirləri mümkün qədər tez paylamaq istəyir.
Açılış mərasiminin keçirildiyi zal dairəvi formada olub, l bərabər sektora bölünmüşdür. Bütün sektorlar ardıcıl olaraq 0-dan l - 1-ə qədər nömrələnmişdir. Beləliklə, hər bir i üçün (0 ≤ i ≤ l - 2) nömrəli sektor i nömrəli sektorun qonşusu i + 1-dir, l - 1 nömrəli sektor isə 0 nömrəli sektorun qonşusudur. Zalda n komanda var. Hər bir komanda bir sektorda oturur. Hər bir sektor istənilən sayda komandanı yerləşdirə bilər. Bəzi sektorlar boş ola bilər.
n ədəd eyni suvenir var. Əvvəlcə Aman və bütün suvenirlər 0 nömrəli sektorda yerləşir. Aman hər komandaya bir suvenir verməli və son suveniri verdikdən sonra 0 nömrəli sektora qayıtmalıdır. Qeyd edək ki, 0 nömrəli sektorda da komandalar ola bilər.
Hər an Aman ən çox k suvenir daşıya bilər. O, suvenirləri 0 nömrəli sektorda götürməlidir və bu, ani baş verir. Hər bir suveniri bir komandaya təhvil verənə qədər daşımaq lazımdır. Aman bir və ya daha çox suvenir daşıyarkən və suvenir almayan komandaların yerləşdiyi sektora çatdıqda, suvenir almayan bir və ya bir neçə komandaya bir suvenir verə bilər. Bu da ani baş verir. Yeganə vaxt tələb edən şey Amanın sektorlar arasında hərəkət etməsidir. Aman hər iki istiqamətdə dairəvi hərəkət edə bilər. Amanın qonşu sektora keçməsi (həm saat əqrəbi istiqamətində, həm də əks istiqamətdə) daşıdığı suvenirlərin sayından asılı olmayaraq dəqiq bir saniyə çəkir.
Sizin vəzifəniz bütün suvenirləri çatdırmaq və başlanğıc mövqeyinə qayıtmaq üçün Amanın nə qədər az vaxt sərf etməli olduğunu tapmaqdır.
Nümunə
Bu nümunədə üç komanda (n = 3) və 8 sektor (l = 8) var, Aman isə əlində iki suvenir (k = 2) tuta bilər. Komandalar 1, 2 və 5 nömrəli sektorlarda yerləşir.
Optimal həllərdən biri şəkildə göstərilmişdir. İlk keçiddə Aman iki suvenir götürür, bir suveniri 2 nömrəli sektordakı komandaya, ikincisini isə 5 nömrəli sektordakı komandaya verir və sonra 0 nömrəli sektora qayıdır. Bu keçid ona 8 saniyə çəkir. İkinci keçiddə Aman qalan suveniri 1 nömrəli sektordakı komandaya çatdırır və 0 nömrəli sektora qayıdır. Bu ona daha 2 saniyə vaxt aparır. Ümumi çatdırılma vaxtı 10 saniyədir.
Giriş məlumatları
Birinci sətir üç ədəd ehtiva edir: komandaların sayı n, Amanın əlində tuta biləcəyi maksimum suvenir sayı k və açılış mərasiminin keçirildiyi zalın sektorlarının sayı l (1 ≤ n ≤ 10^7, 1 ≤ k ≤ n, 1 ≤ l ≤ 10^9). İkinci sətir uzunluğu n olan positions massivini ehtiva edir. positions[0], ..., positions[n - 1] massivinin elementləri hər bir komandanın yerləşdiyi sektorların nömrələrini təyin edir. positions massivinin elementləri artan qaydada sıralanmışdır.
Çıxış məlumatları
Amanın vəzifəni yerinə yetirmək üçün tələb olunan ən az saniyə sayını çıxış edin.