Na takmičenju učestvuje ~N~ takmičara. Zna se da je ~N~ neparan broj. Takmičari su numerisani brojevima od ~1~ do ~N~. Svaki takmičar ~i~ ima svoj nivo veštine ~A_i~. Smatra se da je takmičar koji ima veći nivo veštine bolji. Ukoliko dva takmičara imaju isti nivo veštine bolji je onaj koji je numerisan manjim brojem. Takmičenje se odvija tako što prvo svi takmičari stanu u red, a zatim se odvija sledeći proces:

• Prva tri takmičara u redu se takmiče međusobno. Najlošiji i najbolji takmičar među njima bivaju izbačeni, dok preostali takmičar odlazi na kraj reda.
• To se ponavlja sve dok ne ostane samo jedan takmičar u redu i on se proglašava za pobednika.

~M~ takmičara je poranilo i već su zauzeli svoja mesta u redu. Oni su numerisani brojevima od ~1~ do ~M~. Ostalih ~N-M~ takmičara je došlo tačno na vreme i oni će zauzeti prazna mesta u redu. Oni su numerisani brojevima od ~M+1~ do ~N~. Koji je najveći mogući nivo veštine pobednika ako se takmičari koji nisu poranili rasporede optimalno.

Opis ulaza

• U prvom redu standardnog ulaza nalaze se brojevi ~N~ i ~M~ (~3 \leq N < 10^5~, ~1 \leq M \leq N~).
• U sledećih ~M~ redova nalazi se po 2 broja ~A_i~ i ~P_i~ koji su redom nivo veštine i mesto u redu ~i~-tog takmičara. Svi ~P_i~ su međusobno različiti i važi ~1 \leq P_i \leq N~.
• U sledećih ~N-M~ redova nalazi se po jedan broj ~A_i~, nivoi veštine takmičara koji su stigli tačno na vreme.
• Nivoi veštine takmičara su prirodni brojevi ~1 \leq A_i \leq 10^9~.

Opis izlaza

Na standardni izlaz ispisati najveći mogući nivo veštine pobednika.

Primer ulaza

7 3
5 2
5 5
8 6
6
2
8
9

Primer izlaza

8

Objašnjenje primera

• Na početku u redu stoje takmičari sa rednim brojevima ~1~, ~2~ i ~3~. Red sa praznim mestima izgleda ovako: ~[\_, 5, \_, \_, 5, 8, \_]~. Prazna mesta su obeležena sa ~\_~, a na popunjenim mestima su napisani nivoi veštine takmičara.
• Optimalan raspored takmičara je ~[2, 5, 6, 8, 5, 8, 9]~.
• Proces takmičenja izgleda ovako: ~[2, 5, 6, 8, 5, 8, 9]~ ~=>~ ~[8, 5, 8, 9, 5]~ ~=>~ ~[9, 5, 8]~ ~=>~ ~[8]~