8. Absolútne Pesťahovanie

Medvěd a Dan majú strašne radi psíkov, a sú aj nadšený chovatelia. Po všetkých tých rokov im postupne pribúdali psíky, až ich pomaly nemali kam dávať, lebo im postupne dochádzalo miesto na ich záhradke, keďže novým psíkov vždy treba postaviť na záhradke búdku.

A dnes prišiel ten obávaný deň! Medvěd totiž domov doniesol jedno malé chutnučké šteniatko, ale s Danom zistili, že ho nemajú kam ubytovať! Treba teda rozvrhnúť nový plán bývania.

Po dlhej diskusii sa dohodli, že psíky môžu bývať v novom poschodovom dome, ktorý im teda s Danom postavia niekde na záhrade. Majú dvoch kandidátov - v rohu pri plote, kde je kopa voľného miesta dohora, ale nie príliš do šírky, a pod prístreškom, kde je síce miesta do šírky dosť, ale sú obmedzení strechou. Ešte sa nerozhodli. Čo však určite vedia, je akú vysokú a širokú búdku potrebuje každý psík, a tiež určite vedia, že šetriť na záhradke miestom je úplne maximálne nutné!

Úloha

Dan a Medvěd chcú postaviť panelák pre psíkov. Panelák je zložený z poschodí, ktoré majú tvar obdĺžnika. Každé poschodie má kladnú výšku. Na každom poschodí sa nachádza niekoľko búdiek v rade za sebou, pričom každá búdka má kladnú šírku a výšku. Je zjavné, že poschodie musí byť aspoň tak vysoké ako najvyššia búdka v ňom.

Následne dostanete jeden z dvoch typov otázky. V prvom type máte vypočítať najnižšiu možnú výšku paneláku, pričom šírka paneláku nesmie prekročiť zadanú šírku \(W\). V druhom type máte naopak vypočítať najnižšiu možnú šírku paneláku, pričom výška paneláku nesmie prekročiť zadanú výšku \(H\).

Nakoniec je zadaná postupnosť psíkov. Psíkovia sa musia do domčeka nasťahovať podľa istej hierarchie, a tak im Dan popriradzoval čísla od \(0\) po \(n-1\). Formálne, pre každých dvoch psíkov \(i,j: 0 \leq i < j < n\), musí platiť, že ak psíkovia nebývajú na rovnakom poschodí, tak psík \(i\) býva vyššie, a ak bývajú na rovnakom poschodí, tak psík \(i\) býva viac vľavo. Neformálne, ak by sme búdky prečítali zhora zľava, prečítame ich ako \(0,1,2,3 \dots\)

Vašou úlohou je v závislosti na otázke vypočítať buď najnižší panelák najviac zadanej šírky, alebo najužší panelák najviac zadanej výšky.

Formát vstupu

Na prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^5\)) udávajúce počet psíkov.

Na druhom riadku vstupu je napísané buď sirka alebo vyska podľa toho, či sú Dan a Medvěd obmedzení šírkou, alebo výškou.

Na treťom riadku sa nachádza číslo \(W\) alebo číslo \(H\) \((1 \leq W,H \leq 10^{18})\), teda najväčšia šírka/výška, ktorú si môžu Dan a Medvěd dovoliť.

Nasleduje \(n\) riadkov. Na \(i\)-tom z nich sa nachádzajú čísla \(w_i\) a \(h_i\) \((1 \leq w_i, h_i \leq 10^{12})\) - šírka a výška domčeka pre \(i\)-tého psíka. Vždy je garantované, že sa panelák dá postaviť.

Formát výstupu

Vypíš jeden riadok a v ňom jedno číslo, podľa typu vstupu najnižšiu možnú šírku, alebo výšku paneláku.

Hodnotenie

Je 8 sád testovacích vstupov. V jednotlivých sadách platia nasledujúce obmedzenia:

V tretej a šiestej sade sú všetky otázky typu “sirka”.

Pozor! Teoretické riešenia úlohy môžu získať plný počet iba vtedy, ak ich časová zložitosť závisí iba od \(n\).

Príklady

Input:

5
vyska
10
3 3
5 2
2 3
4 3
2 5

Output:

8

Optimálne je dať psíkov na dve poschodia. Prvé bude mať výšku 3 a budú na ňom bývať prví dvaja psíkovia, druhé bude mať výšku 5 a budú na ňom bývať zvyšní psíkovia.

Input:

5
sirka
10
3 5
5 4
2 4
9 1
1 2

Output:

7