W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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?
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ą.
Napisz program, który:
Uwaga: dany zestaw butli zawsze gwarantuje wykonanie zadania.
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.
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.
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