Programozás‎ > ‎Feladatok‎ > ‎

Tartozás

Ádám tartozik Évának F forinttal. Ismerjük Ádám és Éva pénzjegyeit. Ádám meg szeretné adni a tartozását. Ha nem tudja pontosan megadni, akkor a tartozásból adhat többet úgy, hogy a többletet Éva visszaadja neki a saját pénzéből. 

Feladat

Készíts programot, amely megadja, hogy hogyan tudja megadni Ádám a tartozását úgy, hogy Évának a lehető legkevesebb összeget kelljen visszaadni.

Bemenet

A standard bemenet első sorában Ádám tartozása van (1 ≤ F ≤ 10 000). A második sorban Ádám pénzjegyei száma (1 ≤ N ≤ 100) található. A harmadik sorban Ádám N pénzjegye értéke szerepel (1≤P i ≤1000). A negyedik sorban Éva pénzjegyei száma (1 ≤ M ≤ 100) található. Az ötödik sorban Éva M pénzjegye értéke szerepel (1 ≤ Qi ≤ 1000).

Kimenet

A standard kimenet első sorába azt a legkisebb összeget kell írni, amelyet Évának vissza kell fizetnie! Ha nincs megoldás, akkor az első és egyetlen sorba a -1 számot kell írni. A második sorba első számként a kifizetésben Ádám felhasznált pénzjegyei K számát kell írni, majd annak a K pénzjegynek a sorszámát (tetszőleges sorrendben), amelyekkel Ádám fizet. A harmadik sorba első számként Éva felhasznált pénzjegyei L számát kell írni, majd annak az L pénzjegynek a sorszámát (tetszőleges sorrendben), amelyekkel Éva visszafizet! Több megoldás esetén bármelyik megadható.

Példa

Bemenet  Kimenet
450
4
200 200 300 550
3
10 40 100
50
2 2 3
2 1 2


Tesztadatok

Csatolmányként

Címkék

A feladat forrása: Nemes Tihamér verseny, 2015-2016 2. forduló
Algoritmusok:

megoldás