Budowla

Limit pamięci: 32 MB

W Bajtocji ruszyła rekonstrukcja dawnej budowli. Mimo że budowa potrwa jeszcze wiele miesięcy, to bilety, na pierwszą wizytę wykupiło już wielu mieszkańców. Nie wiadomo jeszcze, ile osób będzie w stanie przebywać w budowli w jednym czasie ze względu na ograniczenia wytrzymałościowe. Będzie to pewna liczba pierwszych w kolejności osób, które wykupiły bilety.

Budowla została zbudowana w specyficzny sposób. W pierwszej kolejności ułożono pewną parzystą liczbę słupów. Następnie na kolejne pary słupów położono płytę. Później na każdej płycie stawiano jeden słup. Następnie ponowiono proces układania płyt - na kolejnych dwóch słupach leżących na płytach najwyższego piętra układano płyty z pojedynczym słupem i tak powstawały kolejne piętra. Projekt był tak zaplanowany, aby na każdym piętrze była parzysta liczba słupów, więc zawsze dawało się zbudować kolejne piętra. Każdy słup ma określoną wytrzymałość, czyli maksymalne obciążenie, jakie może utrzymać.

Uroczyste otwarcie odbędzie się na szczycie budowli, na której zgromadzi się pewna liczba mieszkańców Bajtocji. Łącznie stworzą dość duże obciążenie, równe ich łącznej wadze. Wiadomo, że obciążenie rozkłada się zawsze równomiernie na dwa słupy, podtrzymujące płytę, oraz że płyty mogą wytrzymać dowolne obciążenie.

Rekonstruktor postanowił wymienić pewną liczbę słupów. Po każdej wymianie jednego słupa chciałby wiedzieć, ile maksymalnie osób z kolejki będzie mogło wziąć udział w uroczystym otwarciu. Zakładamy, że waga płyt i słupów jest pomijalnie mała.

Wejście

Pierwszy wiersz standardowego wejścia zawiera trzy liczby całkowite (), oznaczające odpowiednio liczbę pięter budowli, liczbę mieszkańców Bajtocji, którzy wykupili już bilety oraz liczbę słupów do wymiany.

Kolejne wierszy zawiera opisy poszczególnych pięter od najwyższego do najniższego. Kolejne wiersze zawierają liczb całkowitych. W każdym wierszu znajduje się więc liczb całkowitych (), gdzie jest wytrzymałością -tego w kolejności (od lewej) słupa na -tym piętrze (od góry).

W następnym wierszu znajduje się liczb całkowitych (), gdzie oznacza wagę osoby, która jako -ta kupiła bilet.

Kolejne wierszy opisuje wymieniane słupy. Każdy wiersz zawiera trzy liczby całkowite (), oznaczające, że wytrzymałość słupa (od lewej) na piętrze (od góry) zostaje zamieniona na wytrzymałość .

W testach wartych co najmniej punktów zachodzą dodatkowe warunki i .

Wyjście

Standardowe wyjście powinno zawierać wierszy. W kolejnych wierszach powinna znaleźć się jedna liczba całkowita, równa maksymalnej liczbie osób z kolejki, która może wziąć udział w uroczystym otwarciu po wymianie słupów.

Przykład

Dla danych wejściowych:

2 5 3
3 5
6 1 4 3
1 3 5 3 8
1 1 5
2 2 3
1 1 6

poprawną odpowiedzią jest:

2
2
3
3

Autor zadania: Jacek Tomasiewicz.