# Blagajna

V neki daljni deželi plačujejo z bankovci, katerih vrednosti so potence števila $N$ z eksponenti od 0 do vključno $K$. Na primer, če je $N = 3$ in $K = 2$, so na voljo bankovci za 1 dinar ($3^0$), 3 dinarje ($3^1$) in 9 dinarjev ($3^2$).

V omenjeni deželi poslujejo izključno z gotovino. Blagajnik, ki delavcem izplačuje plače, ima na začetku na voljo po $Z$ bankovcev vsake vrednosti. V vrsto se postavi $M$ delavcev, blagajnik pa vsakomur izplača njegovo plačo. Bankovce jemlje po padajočih vrednostih. V našem primeru bi zahtevani znesek izplačal tako, da bi najprej vzel toliko bankovcev za 9 dinarjev, kot je mogoče oziroma kot jih je na voljo, nato bi enako ravnal z bankovci za 3 dinarje, preostanek pa bi izplačal z bankovci za 1 dinar.

Ker je zaloga bankovcev omejena, se lahko zgodi, da naš blagajnik vseh plač ne bo mogel izplačati. Takoj ko ugotovi, da delavcu, ki stoji pred njim, njegove plače ne more v celoti izplačati, pobere šila in kopita, saj ve, da ga ne čaka nič dobrega.

Napiši program, ki na podlagi števil $N$, $K$, $Z$ in $M$ ter plač posameznih delavcev izpiše skupno vrednost denarja, ki ob blagajnikovem pobegu (ali na koncu, če mu uspe vse izplačati) ostane v blagajni.

## Vhod

V prvi vrstici so zapisana cela števila $N$, $K$, $Z$ in $M$. Sledi $M$ vrstic, od katerih vsaka vsebuje po eno celo število. Ta števila predstavljajo plače posameznih delavcev.

## Izhod

Izpiši skupno vrednost bankovcev, ki na koncu ostanejo v blagajni.

## Podnaloge

V vseh testnih primerih velja:

- $2 \le N \le 20$;
- $0 \le K \le 20$;
- $1 \le Z \le 1000$;
- skupna vrednost denarja v blagajni ne presega $10^9$;
- $0 \le M \le 1000$;
- vse plače pripadajo intervalu $[1, 10^9]$.

1. podnaloga (10 točk): $K = 0$.
2. podnaloga (10 točk): $K = 1$.
3. podnaloga (15 točk): vse plače so potence števila $N$ z eksponenti od $0$ do $K$.
4. podnaloga (25 točk): $Z < N$.
5. podnaloga (40 točk): ni dodatnih omejitev.

## Primer

### Vhod

3 2 4 5
30
8
2
4
9

### Izhod

12

### Komentar

Na začetku je v blagajni $4 \cdot 1 + 4 \cdot 3 + 4 \cdot 9 = 52$ dinarjev. Blagajnik mora najprej izplačati 30 dinarjev. V ta namen porabi tri bankovce po 9 dinarjev in en bankovec po 3 dinarje. V blagajni ostane $4 \cdot 1 + 3 \cdot 3 + 1 \cdot 9 = 22$ dinarjev. Nato izplača 8 dinarjev, za kar porabi dva bankovca po 3 dinarje in dva bankovca po 1 dinar. V blagajni ostane še $2 \cdot 1 + 1 \cdot 3 + 1 \cdot 9 = 14$ dinarjev. Blagajnik zatem izplača še tretji znesek (2 dinarja). V blagajni je sedaj $0 \cdot 1 + 1 \cdot 3 + 1 \cdot 9 = 12$ dinarjev. Četrtega zneska (4 dinarje) ne more več izplačati, zato pobegne.