Daşların paylanması

Şəhərin idman kompleksində, ilin istənilən vaxtında tələbələri isidən yeni nəsil sauna quraşdırılıb. Lakin saunanın texnoloji təchizatı o qədər inkişaf edib ki, idman kompleksinin rəhbərliyi onu düzgün şəkildə necə idarə edəcəyini bilmir.

Saunada n - 1 ardıcıl qoşulmuş bölmə var. Hər iki qonşu bölmə arasında n soba yerləşir (hər iki bölmə arasında bir soba, birinci bölmədən əvvəl və sonuncu bölmədən sonra bir soba).

i-ci bölmənin həcmi k[i]-dir və hər sobaya 0-dan v-ə qədər daş yüklənə bilər. i-ci sobada p[i] daş olduğunu qəbul etsək, o zaman i-ci bölməyə k[i] * p[i] * p[i+1] qədər istilik daxil olur.

İdman kompleksinin ixtiyarında s daş var. Rəhbərlik bütün daşları istifadə edərək, lakin kompleksin digər hissəsində çox isti olmaması üçün saunanın bütün bölmələrinə daxil olan ümumi istiliyi minimallaşdırmaq istəyir. Bu problemi həll edin.

Giriş məlumatları

Birinci sətirdə üç tam ədəd n, s və v (2 ≤ n ≤ 1000, 1 ≤ v ≤ 10^5, s ≤ n * v) - soba sayı, daş sayı və hər sobanın tutumu verilmişdir.

İkinci sətirdə n - 1 tam ədəd k[i] - i-ci bölmənin həcmi (1 ≤ k[i] ≤ 10^5) verilmişdir.

Çıxış məlumatları

Tək bir ədəd - bütün bölmələrdə minimal ümumi istiliyi çıxarın.

İzah

Nümunədə düzgün cavab, birinci və dördüncü sobaya dörd daş, ikinci sobaya isə iki daş qoyulduqda əldə edilir. O zaman birinci bölmədən başqa bütün bölmələrdə istilik sıfır olacaq, birinci bölmədə isə səkkiz olacaq.