Andrei este manager la o firmă foarte importantă, la care se lucrează în ture. Aceste ture durează un număr constant de minute (1017 minute), fiecare tură începând la minutul 1. După o tură, Andrei, fiind foarte obosit, doarme până la începutul următoarei ture.

El este foarte ocupat cu o mulțime de ședințe (S ședințe mai exact). Acestea sunt trecute în agenda lui astfel: Minutul de început Durata Minutele necesare pentru pregătire – în minutele de pregătire nu trebuie să îl deranjeze nimeni).

Agenda este foarte dezordonată, iar şedinţele nu sunt notate în ordine cronologică, şi, în plus, acestea se pot suprapune. Ca un bun manager, Andrei doreşte să participe la cât mai multe şedinţe într-o tură cu condiţia să nu se desfăşoare în acelaşi timp. Deoarece nu poate renunța la nicio ședință, el va amâna pentru turele viitoare unele dintre ședințele care se suprapun, păstrând în agendă aceleași informații despre fiecare (început, durată, timp necesar pentru pregătire).

Cerința

a) Afișați numărul minim de ture în care Andrei poate participa la toate şedinţele.
b) Știind că în prima tură, Andrei poate să ajungă la toate şedinţele (nu se desfăşoară două sau mai multe şedinţe la un moment dat), determinați minutul în care se poate programa începutul pregătirii unei noi şedinţe de durată D şi timp de pregătire P, astfel încât să nu se suprapună cu o alta (dacă există mai multe soluţii se va afişa cea cu momentul de început minim).

Date de intrare

Pe prima linie a fişierului de intrare manager.in se găseşte litera a, însemnând că se cere rezolvare cerinţei a), sau b, semnificând faptul că se cere rezolvarea cerinţei b). Pe linia a doua se găseşte un număr S reprezentând numărul de şedinţe, iar pe următoarele S linii se găsesc câte trei numere x y z separate prin câte un spaţiu, astfel: x – minutul la care începe şedinţa de pe linia curentă, y – durata şedinţei iar z – timpul necesar pentru pregătirea şedinţei, în care Andrei nu trebuie să fie deranjat de nimeni. Doar pentru cerinţa b), pe
ultima linie, adică linia S+3, se vor afla 2 numere D P separate printr-un spaţiu, având semnificaţiile din enunţ.

Date de ieșire

Fișierul de ieșire manager.out va conține pe prima linie un singur număr reprezentând răspunsul la cerinţa a sau b dată pe prima linie în fişierul manager.in.

Restricții și precizări

• 1 ≤ D P x y z ≤ 1017
• 1 ≤ S ≤ 100.000
• x-z>0

Exemplul 1

manager.in

a
7
5 8 1
1 3 0
2 4 0
5 9 3
2 7 0
6 10 1
5 1 0

manager.out

6

Explicație

În prima tură se pot desfășura ședințele 2, 7 sau ședințele 2, 6. Toate celelalte ședințe conțin minutul 5 deci vor trebui sa se desfășoare în ture separate astfel: În cea de a doua tură ședința 1, în a treia ședința 3, în cea de-a patra ședința 4, într-a cincea ședința 5, iar într-a șasea ședința 6 sau 7 în funcție de cea aleasă pentru tura 1. În total sunt 6 ture.

Exemplul 2

manager.in

b
6
5 3 2
20 6 3
48 10 4
10 5 0
30 3 1
55 3 3
7 1

manager.out

33

Explicație

Pregătirea noii ședință poate începe de la minutul 33, între ședințele 5 și 3.