Płetwonurek
Limit pamięci: 32 MB
Płetwonurek do nurkowania używa butli, w której są dwa zbiorniki: z tlenem i z azotem.
W zależności od czasu przebywania pod wodą i głębokości nurek potrzebuje różnych ilości tlenu i azotu.
Płetwonurek ma do dyspozycji pewną liczbę butli.
Każda butla charakteryzuje się wagą oraz objętością zawartego w niej tlenu i azotu.
Do wykonania zadania nurek potrzebuje określonych ilości tlenu i azotu.
Jaka jest najmniejsza sumaryczna waga butli, które nurek musi zabrać ze sobą, żeby mógł wykonać zadanie?
Przykład
Nurek ma do dyspozycji butli o następujących charakterystykach
(odpowiednio: objętość tlenu w litrach, objętość azotu w litrach, waga butli w dekagramach):
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
Jeżeli do wykonania zadania nurek potrzebuje litrów tlenu i litrów azotu,
to musi zabrać ze sobą dwie butle o łącznej wadze , np. pierwszą i drugą lub czwartą i piątą.
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia zapotrzebowanie nurka na tlen i azot, liczbę dostępnych butli oraz ich charakterystyki;
- oblicza najmniejszą sumaryczną wagę butli, które nurek musi zabrać ze sobą, żeby wykonać zadanie;
- zapisuje wynik na standardowe wyjście.
Uwaga: dany zestaw butli zawsze gwarantuje wykonanie zadania.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i ,
oddzielone pojedynczym odstępem, i .
Są to, odpowiednio, ilości tlenu i azotu potrzebne do wykonania zadania.
Drugi wiersz pliku wejściowego zawiera tylko jedną liczbę , .
Jest to liczba dostępnych butli.
Kolejne wierszy zawiera charakterystyki butli.
Wiersz zawiera trzy liczby całkowite , pooddzielane pojedynczymi odstępami (, , ).
Są to kolejno: objętości tlenu i azotu w -tej butli oraz waga tej butli.
Wyjście
Twój program powinien zapisać jedną liczbę całkowitą w pierwszym i jedynym wierszu standardowego wyjścia.
Tą liczbą powinna być najmniejsza sumaryczna waga butli, które nurek musi zabrać ze sobą, żeby mógł wykonać zadanie.
Przykład
Dla danych wejściowych:
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
poprawną odpowiedzią jest:
249