Coinholt Çörəkçisi və Minimum Qəpik

Sehrli Coinholt kəndindəki çörək sobanızın arxasında dayanıb təzə bişmiş şirniyyatları düzürsünüz. Qapı açılır və içəri keyfiyyətli mallara xüsusi diqqəti olan bacarıqlı tacir Denara daxil olur. O, sürətli bir yeməkdən sonra masanın üzərinə 100 vahid dəyərində parıldayan bir sikkə qoyur.

Gülümsəyərək sikkəni götürürsünüz və yeməyin ümumi dəyərinə baxırsınız: 88 vahid. Bu o deməkdir ki, siz ona 12 vahid qalıq qaytarmalısınız. Denara əlini uzadaraq gülümsəyir: "Mənə sadəcə ən az sayda qəpik ver. Kisəm onsuz da doludur və onları yolda itirmək istəmirəm."

Siz bilirsiniz ki, kassanızda fərqli dəyərlərə malik qəpiklər var (məsələn: 10 vahidlik Lumis, 5 vahidlik Viras və 2 vahidlik Zenth). Beyninizdə dərhal ehtimalları hesablayırsınız:

• 1 Lumis (10) + 1 Zenth (2) = Cəmi 2 qəpik.

• 2 Viras (5x2) + 1 Zenth (2) = Cəmi 3 qəpik.

• 6 Zenth (6x2) = Cəmi 6 qəpik.

"Ən yaxşı seçim iki qəpikdir: bir Lumis və bir Zenth," deyərək qalığı ona uzadırsınız. Denara məmnun halda gülümsəyir: "Həmişəki kimi, yenə də ən doğrusunu tapdın."

Sizin vəzifəniz müştəriyə veriləcək qalığın məbləği və kassanızdakı mövcud qəpik növləri verildikdə, cəmi tam olaraq qalıq məbləğinə bərabər olan ən az sayda qəpiyi tapan proqram yazmaqdır. Qeyd: Hər qəpik növündən kassanızda sonsuz sayda olduğunu fərz edin.

Giriş verilənləri: Birinci sətirdə kassanızdakı fərqli qəpik növlərinin sayını bildirən N və qaytarılmalı olan qalıq məbləğini bildirən M tam ədədləri verilir. İkinci sətirdə isə aralarında boşluq olmaqla N ədəd fərqli qəpik dəyərləri verilir.

Çıxış verilənləri: Qalıq kimi veriləcək qəpiklərin dəyərlərini kiçikdən böyüyə sıralanmış şəkildə, aralarında boşluq olmaqla tək sətirdə çap edin. Əgər verilmiş qəpiklərlə məbləği düzəltmək mümkün deyilsə (məsələn, yalnız 2 və 5 vahidlik qəpikləriniz varsa, amma qalıq 3-dürsə), -1 çap edin. Əgər birdən çox optimal (ən az saylı) kombinasiya varsa, kiçik nominalı daha kiçik olan kombinasiyanı çap edin.