Županijsko natjecanje iz informatike 2021. / Prva podskupina (1. i 2. razred) - 3. zadatak

Scamazon je popularna tvrtka koja svojim korisnicima omogućuje kupovinu raznih proizvoda putem interneta. Kupovina preko Scamazona funkcionira na sljedeći način:

• Korisnik (engl. user, pogrdno loser) nakon registracije uplati Scamazonu određen broj kuna. Označimo taj broj sa x.

• Scamazon potom korisniku dodijeli k virtualnih novčanica u vrijednosti od c1, c2, . . . , ck kuna. Naravno, suma vrijednosti tih novčanica jednaka je x.

• Korisnik tada može pretraživati razne proizvode i dodavati ih u svoju virtualnu košaricu. Iz košarice korisnik ne može izbacivati proizvode, ali ih može sve zajedno kupiti.

• U svakom trenutku korisnik može kupiti cijeli sadržaj košarice tako da iskoristi točno jednu novčanicu čija je vrijednost veća ili jednaka sumi vrijednosti proizvoda koji se nalaze u košarici. Košarica se tada prazni, a virtualna novčanica nestaje. Odnosno, Scamazon korisniku ne vraća ostatak prilikom kupnje.

• Nakon završetka kupovine (kada napusti stranicu), korisnik natrag dobiva novac s neiskorištenih novčanica.

Mirko se ulogirao u Scamazon, proučio pravila kupovine te odlučio kojih će n proizvoda kupiti i kojim će ih redom dodavati u virtualnu košaricu.

Odredite koliko mu najviše novaca može ostati na kraju kupnje kada bi optimalno baratao novčanicama koje mu je dodijelio Scamazon ili odredite da nije moguće kupiti svih n proizvoda koristeći dane novčanice.

Ulazni podaci

U prvom je retku broj n (1 ≤ n ≤ 200 000) iz teksta zadatka.

U drugom je retku n brojeva ai (1 ≤ ai ≤ 109) koji predstavljaju vrijednosti proizvoda koje je Mirko odlučio kupiti i to redom kojim će ih dodavati u virtualnu košaricu.

U trećem je retku broj k (1 ≤ k ≤ 20) iz teksta zadatka.

U četvrtom je retku k brojeva ci (1 ≤ ci ≤ 109) iz teksta zadatka.

Izlazni podaci

Ako Mirko ne može kupiti sve željene proizvode, ispišite NEMOGUCE. U protivnom, ispišite traženu svotu novca iz teksta zadatka.

Primjer zadatka

Ulaz

10
1 2 3 4 5 6 7 8 9 10
4
20 20 20 20

Izlaz

0

Objašnjenje

Pojašnjenje prvog probnog primjera:

• Prvom novčanicom od 20 kuna Mirko kupuje proizvode u vrijednosti od 1 + 2 + 3 + 4 + 5 = 15 kuna.
• Drugom novčanicom od 20 kuna Mirko kupuje proizvode u vrijednosti od 6 + 7 = 13 kuna.
• Trećom novčanicom od 20 kuna Mirko kupuje proizvode u vrijednosti od 8 + 9 = 17 kuna.
• Četvrtom novčanicom od 20 kuna Mirko kupuje posljednji proizvod u vrijednosti od 10 kuna.

Ulaz

10
3 3 3 3 3 3 3 3 3 3
5
8 9 11 20 3

Izlaz

19

Objašnjenje

Pojašnjenje drugog probnog primjera:

• Drugom novčanicom od 9 kuna Mirko kupuje prva tri proizvoda.
• Četvrtom novčanicom od 20 kuna Mirko kupuje idućih šest proizvoda.
• Petom novčanicom 3 kune Mirko kupuje posljednji proizvod.
• Budući da su prva i treća novčanica ostale neiskorištene, Mirku će ostati 8 + 11 = 19 kuna

Ulaz

6
3 7 5 1 2 9
8
2 5 8 9 4 3 5 1

Izlaz

9

Objašnjenje

Pojašnjenje trećeg probnog primjera:

• Šestom novčanicom od 3 kune Mirko kupuje prvi proizvod.
• Trećom novčanicom od 8 kuna Mirko kupuje drugi proizvod.
• Drugom novčanicom od 5 kuna Mirko kupuje treći proizvod.
• Osmom novčanicom od 1 kune Mirko kupuje četvrti proizvod.
• Prvom novčanicom od 2 kune Mirko kupuje peti proizvod.
• Četvrtom novčanicom od 9 kuna Mirko kupuje šesti proizvod.
• Budući da su peta i sedma novčanica ostale neiskorištene, Mirku će ostati 4 + 5 = 9 kuna.