Sentlərin qənaəti

Regional yarışmaya, məsələn, NWERC üçün hazırlıq tələb olunur: otaqların və kompüterlərin təşkili, yaxşı tapşırıq dəstinin yaradılması, iştirakçıların dəvət edilməsi, köynəklərin dizaynı, otel otaqlarının rezervasiyası və s. Mən supermarketdə alış-verişə cavabdehəm.

Kassaya çatanda, bütün n əşyalarımı konveyerə qoyuram və məndən əvvəl növbədə olan bütün digər müştərilərin xidmət edilməsini gözləyirəm. Gözləyərkən başa düşürəm ki, bu supermarket son zamanlarda alış-verişin ümumi qiymətini 10 sentin ən yaxın qatına yuvarlamağa başlayıb (əgər 5 sentdirsə, yuxarıya yuvarlanır). Məsələn, 94 sent 90 sentə, 95 sent isə 100 sentə yuvarlanacaq.

Alış-verişimi qruplara bölüb ayrı-ayrılıqda ödəyə bilərəm. d ayırıcı tapıb alış-verişi d + 1 qrupa bölə bildim. Ayırıcıları harada yerləşdirmək lazım olduğunu bilmək istəyirəm ki, bütün alış-verişlərin ümumi dəyərini minimuma endirim. Vaxtım azaldığı üçün lentdəki əşyaları yenidən düzəltmək istəmirəm.

Giriş Məlumatları

Bunlardan ibarətdir:

• bir sətir iki ədəd n (1 ≤ n ≤ 2000) və d (1 ≤ d ≤ 20) - alış-verişlərin sayı və mövcud ayırıcıların sayı;

• bir sətir n tam ədəd p[1], ..., p[n] (1 ≤ p[i] ≤ 10000 üçün 1 ≤ i ≤ n) - alış-verişlərin sentlərlə qiymətləri. Qiymətlər lentdəki alış-verişlərin yerləşdiyi ardıcıllıqla verilir.

Çıxış Məlumatları

d ayırıcıdan istifadə edərək bütün məhsulları almaq üçün lazım olan ən az miqdarda pulu çıxarın.