En Marc està jugant als seus jocs de mòbil i contínuament li surt el mateix anunci del mateix joc de mòbil. Que a més jo sé que aquest joc després me’l baixaré i no tindrà res que veure amb l’anunci, però mira, jo que sé, l’anunci sembla interessant.

En aquest anunci mega-famós, tens un personatge, així com \(N\) \((1 \le N \le 1000)\) monstres, en diversos punts al llarg d'un camí, que es pot representar com una línia numèrica. La posició inicial d'en Marc al llarg del camí és \(S\) \((1 \le S \le 100,000)\), mentre que la posició de cada monstre és \(P\) \((1 \le P \le 100,000)\). Totes aquestes posicions són diferents.

En Marc pot caminar en qualsevol direcció, cap endavant o cap enrere pel camí. Tanmateix, cada vegada que arriba a la mateixa ubicació que un monstre, és impossible passar de llarg: ha de lluitar contra ell.

El nivell inicial del personatge després d’haver sigut estimbat per alguna gegant amb poca roba és \(L (1 \le L \le 100,000)\), mentre que el nivell de cada monstre és \(M (1 ≤ M ≤ 100,000)\). Marc pot derrotar un monstre si el nivell actual del seu personatge és més gran o igual que el nivell d'aquest monstre. Si el personatge derrota al monstre, el nivell actual del personatge augmentarà en \(G (1 ≤ G ≤ 100,000)\), i aquest monstre desapareixerà i ja no ocuparà cap punt del camí.

En Marc mai no farà que el personatge lluiti contra un monstre el nivell del qual sigui més gran que el nivell del seu personatge, ja que moriria i ja no podria jugar a l’anunci i s’hauria de descarregar el joc.

Quin és el nivell màxim possible que en Marc pot ajudar al personatge a aconseguir, triant de manera òptima com caminar pel camí.

Entrada

La primera línia d'entrada consisteix en un únic enter, \(N\). La següent línia consisteix en dos enters separats per espais, \(S\) i \(L\). Segueixen \(N\) línies, cadascuna d’elles formada per 3 enters, \(P, M \) i \( G\)

Sortida

Escriu un únic enter, el nivell màxim possible que el personatge de Marc pot aconseguir.

Exemple d'Entrada 1

5 
8 5 
3 9 2 
19 2 9 
12 6 8 
5 2 1 
15 17 3

Exemple de Sortida 1

16

Explicació Exemple

Aquesta entrada representa el següent gràfic (a on el Personatge està en blau)

En Marc es pot moure cap a l'esquerra fins a la posició 5, i derrotar el monstre allà per augmentar el nivell del seu personatge a 6. Després pot moure's cap a la dreta fins a la posició 12, derrotant el monstre allà i augmentant el nivell del seu personatge a 14. Finalment, pot derrotar el monstre a la posició 3 per augmentar el nivell del seu personatge a 16. Aquest és el nivell més alt que el personatge podria arribar a assolir.