Alex doreste sa inchirieze servere pentru a acoperi o capacitate totala necesara. Exista 3 tipuri de servere disponibile, fiecare caracterizat de un pret si o capacitate. Alex poate inchiria oricate servere doreste, de oricare tip, in orice combinatie (indiferent daca sunt sau nu de acelasi tip).
Care este costul minim cu care Alex poate inchiria servere astfel incat suma capacitatilor lor sa fie cel putin C?
- Date de intrare
- Pe fiecare dintre primele 3 linii se citesc cate doua numere intregi pret si capacitate, pentru cele 3 tipuri de servere. Pe a patra linie se citeste numarul intreg C, capacitatea minima ceruta.
- Date de iesire
- Se afiseaza un singur numar intreg: costul minim total.
- Restrictii
- 1 <= pret <= 1000 1 <= capacitate <= 1000 1 <= C <= 20000
Exemple
Exemplul 1
Intrare
2 2 5 10 10 23 1000
Iesire
437
Exemplul 2
Intrare
2 2 5 10 10 23 1
Iesire
2