Statki kosmiczne
Limit pamięci: 32 MB
Generałowie sił powietrznych Bajtocji: Bajtek, Kajtek i Zajtek zamierzają przeprowadzić
pierwszą w historii Bajtocji wielką wyprawę kosmiczną.
Każdy z nich zgromadził już pewną ilość paliwa rakietowego i właśnie szykują się na zakup
modułów, z których złożą rakietę.
Bajtockie rakiety są skonstruowane w ten sposób, że w początkowym fragmencie lotu są napędzane
tylko przez pierwszy moduł, po zużyciu się paliwa w tym module zostaje on odrzucony i odtąd
napędu rakiecie dostarcza drugi moduł itd.
Każdy z generałów odwiedzi dzisiaj swoją ulubioną fabrykę i zakupi
moduł z silnikiem rakietowym o pewnej sprawności; z tych trzech modułów ustawionych w ustalonej
kolejności (Bajtek kupuje dolny, Kajtek - środkowy, a Zajtek - górny) zostanie
złożona rakieta.
Maksymalny zasięg tej rakiety (tj. największa odległość, na jaką może ona dolecieć) będzie równy
sumie zasięgów poszczególnych modułów, z których każdy jest wyrażony jako iloczyn sprawności
silnika oraz objętości zatankowanego do modułu paliwa.
Ze względu na wzrastające ceny w fabrykach, generałowie być może nie zakupią
modułów o największych sprawnościach.
Chcieliby więc poznać liczbę różnych trójek modułów, które mogą zakupić (każdy generał po jednym
module ze swojej fabryki), takich że złożona z nich rakieta będzie miała zasięg większy niż połowa
zasięgu najlepszej rakiety, jaka mogłaby powstać przy aktualnym asortymencie fabryk,
tj. gdyby każdy generał kupił najsprawniejszy moduł.
Różne moduły o tych samych sprawnościach są przy zliczaniu uznawane za różne.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia
asortymenty fabryk, które odwiedzą generałowie oraz ilości paliwa rakietowego, jakie posiadają,
- obliczy liczbę trójek modułów spełniających wymogi Bajtka, Kajtka i Zajtka,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się trzy liczby całkowite , oraz (),
pooddzielane pojedynczymi odstępami i oznaczające objętości paliwa posiadane odpowiednio przez Bajtka, Kajtka i Zajtka.
Dalej następują opisy fabryk odwiedzonych przez generałów (pierwsza to fabryka
odwiedzona przez Bajtka, druga - przez Kajtka, a trzecia - przez Zajtka).
Każdy opis składa się z dwóch wierszy.
W pierwszym z nich znajduje się jedna liczba całkowita (dla ),
oznaczająca liczbę modułów dostępnych w fabryce. Drugi i jednocześnie ostatni wiersz opisu
fabryki składa się z pooddzielanych pojedynczymi odstępami liczb całkowitych dodatnich
nie większych od , oznaczających sprawności poszczególnych modułów z fabryki.
Wyjście
W pierwszym i jedynym wierszu wyjścia Twój program powinien wypisać liczbę możliwych do stworzenia rakiet,
których zasięg będzie większy od połowy maksymalnego zasięgu.
Przykład
Dla danych wejściowych:
2 3 3
2
1 3
3
1 5 1
1
2
poprawną odpowiedzią jest:
4
Wyjaśnienie do przykładu: Maksymalny możliwy zasięg rakiety to ,
więc szukamy trójek modułów o zasięgu większym niż .
Są to: , , , , o odpowiadających im zasięgach: , , , .
Uwaga: Możesz założyć, że w 40% testów dla każdego jest spełniony warunek .
Autor zadania: Tomasz Kulczyński.