Ксероксinator

Doktor Hayns Fufelşmerts növbələrdə dayanmaqdan bezib. Buna görə də, insan klonları yaradan kseroksinator adlı bir cihaz icad edib. İndi o, klonlarını öz yerinə növbələrdə dayanmağa göndərir. Təəssüf ki, cihazda gözlənilməz bir nasazlıq baş verib və nəticədə çoxlu sayda klon yaranaraq hamısı poçta gedir.

Bu gün poçt n dəqiqə ərzində işləyir və bu dəqiqələr 1-dən n-ə qədər nömrələnib. i-ci dəqiqənin əvvəlində poçta a[i] sayda Fufelşmerts klonu gəlir və növbənin sonuna dayanır. Bir dəqiqə ərzində poçtda ən çox b klon xidmət ala bilər - əgər növbədə ən azı b klon varsa, ilk b klon xidmət alır, əks halda növbədə olanların hamısı xidmət alır. i-ci dəqiqədə xidmət alan bütün klonlar i-ci dəqiqənin sonunda poçtdan çıxır. n-ci dəqiqənin sonunda poçt bağlanır. Xidmət ala bilməyən bütün klonlar bir dəqiqə narazı dayanır və sonra dağılışır. Haynsa bütün klonların poçtda keçirdiyi ümumi vaxtı hesablamağa kömək edin.

Diqqət yetirin ki, əgər klon i-ci dəqiqənin əvvəlində poçta daxil olub və i-ci dəqiqənin sonunda çıxıbsa, o, poçtda bir dəqiqə keçirmişdir.

Giriş məlumatları

Birinci sətirdə iki tam ədəd n və b (1 ≤ n ≤ 10^5, 1 ≤ b ≤ 10^8) - poçtun işlədiyi dəqiqələrin sayı və bir dəqiqə ərzində xidmət ala bilən klonların sayı verilir.

İkinci sətirdə n tam ədəd a[i] (0 ≤ a[i] ≤ 10^8) - i-ci dəqiqənin əvvəlində poçta gələcək klonların sayı verilir.

Çıxış məlumatları

Bir tam ədəd çıxarın - bütün klonların poçtda keçirdiyi ümumi vaxt.