Endirim kuponları

Mağazalarda bütün mallara 15 May — Axmaqlar Günü münasibətilə endirim edilir. Bu o deməkdir ki, qiyməti $X$ manat olan bir məhsulu you $Y$ endirim kuponu təqdim edərək aşağıdakı qiymətə ala bilərsiniz:

manat. Sizin $M$ endirim kuponunuz var və $N$ məhsul almaq istəyirsiniz. Hər məhsulun qiyməti A_1, A_2, \dots, A_N olaraq verilir. Bütün məhsulları almaq üçün minimum nə qədər pul lazımdır?

Qeyd: Burada $\lfloor X\rfloor$, $X$ ədədinin tam hissəsini göstərir.

Giriş

Birinci sətrdə iki tam ədəd $N$ və $M$ (1 \leq N, M \leq 10^5), ikinci sətrdə $N$ tam ədəd A_1, A_2, \dots, A_N (1 \leq A_i \leq 10^9) verilib.

Çıxış

Bütün məhsulları almaq üçün tələb olunan minimum pul miqdarını çap edin.

Alt tapşırıqlar

Bu məsələ $5$ alt tapşırıqdan ibarətdir:

Nümunənin izahı

• Birinci nümunədə bütün məhsulları $10$ manata almaq olar: birinci məhsul heç bir kupon təqdim etmədən $3$ manata, ikinci məhsul $2$ kuponla

  \left\lfloor \frac{15}{2^2} \right\rfloor = 3

  manata, üçüncü məhsul isə $1$ kuponla $4$ manata alınır. Toplam: 3 + 3 + 4 = 10 manat.

• İkinci nümunədə $1000$ kupondan istifadə edərək, $1000000$ manatlıq məhsulu $0$ manata ala bilərsiniz.