Historia OI -> XIII OI 2005/2006

SIO

MAIN

Zadanie: Krążki

Dostępna pamięc: 32MB

Mały Jaś dostał od rodziców na urodziny nową zabawkę, w której skład wchodzą rurka i krążki. Rurka ma nietypowy kształt -- mianowicie jest to połączenie pewnej liczby walców (o takiej samej grubości) z wyciętymi w środku (współosiowo) okrągłymi otworami różnej średnicy. Rurka jest zamknięta od dołu, a otwarta od góry. Na poniższym rysunku przedstawiono przykładową taką rurkę, złożoną z walców, w których wycięto otwory o średnicach kolejno: 5cm, 6cm, 4cm, 3cm, 6cm, 2cm i 3cm.

$\includegraphics{kra1}% WIDTH=277 HEIGHT=162$ Krążki w zabawce Jasia są walcami o różnych średnicach i takiej samej grubości co walce tworzące rurkę.

Jaś wymyślił sobie następującą zabawę. Mając do dyspozycji pewien zestaw krążków zastanawia się, na jakiej wysokości zatrzymałby się ostatni z nich, gdyby wrzucał je kolejno do rurki centralnie (czyli dokładnie w jej środek). Dla przykładu, gdyby wrzucić do powyższej rurki krążki o średnicach kolejno 3cm, 2cm i 5cm, to otrzymalibyśmy następującą sytuację:

$\includegraphics{kra2}% WIDTH=277 HEIGHT=162$ Jak widać, każdy kolejny krążek po wrzuceniu spada dopóki się nie zaklinuje (czyli nie oprze się o walec, w którym wycięty jest otwór o mniejszej średnicy niż średnica krążka), albo nie natrafi na przeszkodę w postaci innego krążka lub dna rurki.

Ponieważ zabawa ta jest trudna dla małego Jasia, to ciągle prosi swoich rodziców o pomoc. A jako że rodzice Jasia nie lubią takich zabaw intelektualnych, to poprosili Ciebie -- znajomego programistę -- o napisanie programu, który zamiast nich będzie udzielał odpowiedzi Jasiowi.

Zadanie

Napisz program, który:

wczyta ze standardowego wejścia schemat rurki i opis krążków jakie Jaś będzie wrzucał do rurki,
wyznaczy głębokość, na jakiej zatrzyma się ostatni wrzucony przez Jasia krążek,
wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite n i m ( 1 $$ \le$% WIDTH=16 HEIGHT=30$ n, m $$ \le$% WIDTH=16 HEIGHT=30$ 300 000), oddzielone pojedynczym odstępem i oznaczające wysokość rurki Jasia (liczbę walców wchodzących w jej skład) i liczbę krążków, które zamierza wrzucić do rurki. Drugi wiersz wejścia zawiera n liczb całkowitych r₁, r₂,...r_n ( 1 $$ \le$% WIDTH=16 HEIGHT=30$ r_i $$ \le$% WIDTH=16 HEIGHT=30$ 1 000 000 000 dla 1 $$ \le$% WIDTH=16 HEIGHT=30$ i $$ \le$% WIDTH=16 HEIGHT=30$ n) oddzielonych pojedynczymi odstępami i oznaczających średnice otworów wyciętych w kolejnych (od góry) walcach tworzących rurkę. Trzeci wiersz wejścia zawiera m liczb całkowitych k₁, k₂,..., k_m ( 1 $$ \le$% WIDTH=16 HEIGHT=30$ k_j $$ \le$% WIDTH=16 HEIGHT=30$ 1 000 000 000 dla 1 $$ \le$% WIDTH=16 HEIGHT=30$ j $$ \le$% WIDTH=16 HEIGHT=30$ m) oddzielonych pojedynczymi odstępami i oznaczających średnice kolejnych krążków, które Jaś zamierza wrzucić do rurki.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą głębokość zatrzymania się ostatniego krążka. Jeżeli krążek ten w ogóle nie wpadnie do rurki, to odpowiedzią powinna być liczba 0.

Przykład

Dla danych wejściowych:

7 3
5 6 4 3 6 2 3
3 2 5

poprawną odpowiedzią jest:

Wersja do druku