Hydra
Limit pamięci: 128 MB
Bituś dostał na urodziny grę komputerową o nazwie Niesamowite przygody Rycerza Bajtazara.
Zabawa polega na kierowaniu postacią tytułowego rycerza, który przemierza
królestwo Bajtocji i pomaga uciśnionym przez poczwary, poborców podatkowych i gradobicia.
Bituś przeszedł już prawie całą grę, ale utknął na ostatnim poziomie, w którym
Bajtazar walczy z wielkim morskim wężem - Bajtocką Hydrą.
Do walki z potworem Bajtazar używa swojego miecza.
W grze dostępne są dwa rodzaje ciosów: rycerz może albo uciąć głowę węża,
albo (co oczywiście wymaga więcej wysiłku) zmasakrować tę głowę.
Jednakowoż ucięcie głowy węża, choć prostsze, powoduje, że w miejscu odcięcia z szyi węża odrastają nowe głowy.
Wodny potwór zostanie pokonany dopiero wtedy, gdy Bajtazar pozbawi go wszystkich głów
i żadna głowa nie będzie już mogła odrosnąć.
Bajtocka Hydra może mieć rodzajów głów, które będziemy oznaczali liczbami od 1 do .
Na samym początku wąż ma jedną głowę rodzaju 1.
Głowa rodzaju (dla ) charakteryzuje się następującymi cechami:
liczbą machnięć miecza , które musi wykonać Bajtazar, aby uciąć tę głowę,
liczbą machnięć miecza , która jest wymagana do zmasakrowania tej głowy,
oraz listą rodzajów głów , które odrastają na miejsce głowy rodzaju
po jej ucięciu.
Podpowiedz Bitusiowi, ile minimalnie machnięć mieczem należy wykonać, aby pokonać Hydrę.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (),
oznaczająca liczbę rodzajów głów Hydry.
Kolejne wierszy opisuje poszczególne rodzaje głów; w -tym z tych wierszy
opisana jest głowa rodzaju .
Wiersz ten zaczyna się trzema liczbami całkowitymi , ,
(, ), po których następują liczby całkowite
().
Suma liczb nie przekracza .
Wyjście
W jedynym wierszu wyjścia należy wypisać minimalną liczbę machnięć mieczem,
która jest potrzebna, by wygrać grę.
Przykład
Dla danych wejściowych:
4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2
poprawną odpowiedzią jest:
26
Autor zadania: Tomasz Idziaszek.