8. Ako Jemo Etku spoznal

V krajine, kde sa na strednej škole delilo nulou a prvočísla rozkladali na čísla zložené, žila Etka. Etka bola už od mala šikovná, veď už na základnej škole písala Raabeho testy na plný počet. A tak si jedného dňa povedala, že aj ona ide zlepšiť svet a začne priamo v Tesku pri výklade s kryptomenami.

Na druhej strane kopca bola tiež vyspelá krajina. Mala tri kruhové objazdy, štyri semafory a pelikána v erbe. A v tejto krajine plnej šikovných ľuďí si nažíval, nie síce múdry, ale zato vysoký, Jemko. Jedného dňa ale prerástol celé svoje okolie natoľko, že musel ísť hľadať svoje šťastie cez kopec. Tu sa rýchlo priučil remeslu delenia nulou, no aj tak nikdy nezapadol medzi ostatných ľudí. Predsa len ale prišiel deň, ktorý mu navždy zmenil život.

Jedného zimného večera, keď Jemo opäť vyhladol a dojedol zbytky aj v susedovej chladničke, sa rozhodol ísť dokúpiť zásoby do neďalekého Teska. A tu Jemko zbadal prekrásnu Etku obsluhujúcu pult s kryptomenami. Okamžite sa tam vybral. Romýšľajúc, ako Etku očariť, mu v hlave skrsol geniálny nápad.

Ženu určite očarí bohatý muž, preto sa Jemo rozhodol, že za peniaze, ktoré má, toho nakúpi najviac, ako len môže. Ako ale všetci vieme, kryptomien je straaašne veľa a Jemko ani len nedovidí z jedného konca pultu na druhý. Navyše, Jemko vôbec žiadne kryptomeny nepoznal. Chcel to ale zahrať na odborníka, a tak sa rozhodol, že kúpi len z tých kryptomien, na ktorých názov dovidí. Čo si ale Jemko všimol je, že pri pulte s kryptomenami bola z každej kryptomeny len \(1\) minca. Nechcel Etku posielať hľadať ďalšie do skladu, takže sa rozhodol, že kúpi z každej kryptomeny najviac \(1\) mincu. Horšie zistenie bolo to, že Tesko má úplne iné ceny ako hodnoty kryptomien na trhu. Aby neskončil úplne na mizine, rozhodol sa zo svojho rozpočtu nakúpiť tak, že to možno nebude najdrahší nákup čo vie spraviť, ale bude mať najväčšiu hodnotu na trhu.

Takto večer už bola Etka veľmi unavená a tak Jemkovi nevenovala pozornosť. No Jemo sa len tak nevzdal. Rozhodol sa, že tam bude chodiť znova a znova hoc aj \(10\,000\)-krát a opakovať to, čo urobil posledný večer. Až kým si jej srdce nezíska.

No napriek tomu, že Jemko pôjde cez leto hľadať bugy do švajčiarskych končín, má problémy s vypočítaním najlepšieho nákupu. A Etka je veľmi inteligentné dievča, ak by nenakúpil optimálne, hneď by si to všimla a jeho šanca by bola v háji. Pomôžete mu?

Úloha

V Tesku predávajú \(n\) kryptomien. Kryptomeny sú vyložené na pulte v jednom dlhom rade. Každá kryptomena má nejakú cenu v obchode a nejakú hodnotou na trhu. Jemko obchod navštívi \(q\)-krát. Pretože ale chodí vždy večer, na pulte je vždy z každej meny už len \(1\) minca. Pre každú návštevu vieme, koľko má Jemo peňazí v peňaženke a odkiaľ pokiaľ vidí, a zaujíma nás odpoveď na otázku: “Akú najväčšiu hodnotu vie Jemo nakúpiť, ak jediné peniaze, čo má k dispozícii, sú tie v jeho peňaženke, a vyberá si len medzi menami, na ktoré dovidí?”

Formát vstupu

V prvom riadku sú 2 celé čísla \(n, q\) oddelené medzerou: počet rôznych kryptomien a počet návštev. Kryptomeny sú očíslované od \(1\) po \(n\).

Nasleduje \(n\) riadkov, v každom sú dve medzerou oddelené celé čísla \(c_i, h_i\): cena \(i\)-tej kryptomeny v Tesku a hodnota tejto kryptomeny na trhu.

Na konci bude \(q\) riadkov popisujúcich Jemkove návštevy. V každom je trojica čísel \(l_i, r_i, p_i\) oddelených medzerou, hovoriacich, že Jemko má v peňaženke \(p_i\) peňazí a môže nakupovať kryptomeny od \(l_i\) po \(r_i\), vrátane.

Formát výstupu

Pre každú Jemovu návštevu Teska vypíšte jeden riadok a v ňom jedno celé číslo: najväčšiu hodnotu, ktorú vie Jemo nakúpiť.

Hodnotenie

Pre jednotlivé sady vstupov platia nasledovné obmedzenia

Príklady

Input:

3 2
2 2
3 3
2 2
1 3 4
1 2 4

Output:

4
3

Input:

3 2
2 2
3 5
2 2
1 3 4
1 2 4

Output:

5
5