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.