Woburn Challenge 2018-19 Round 3 - Junior Division

Jessie loves her Arbok, but the poor snake seems to not have much luck winning any battles. Jessie's decided to turn things around by helping Arbok level up! There's no better way to train than going around and defeating wild Pokémon who are just minding their own business, so that's exactly what Jessie intends on doing.

Jessie and her Arbok, as well as ~N~ ~(1 \le N \le 1\,000)~ wild Pokémon, are all standing at various points along a trail, which can be represented as a number line. Jessie's initial position along the trail is ~S~ ~(1 \le S \le 100\,000)~, while the ~i~-th wild Pokémon's position is ~P_i~ ~(1 \le P_i \le 100\,000)~. All ~N + 1~ of these positions are distinct.

Jessie can walk in either the positive or negative direction along the trail. However, whenever she arrives at the same location as a wild Pokémon, sneaking by is out of the question - she must have Arbok battle it.

Arbok's initial level is ~L~ ~(1 \le L \le 100\,000)~, while the ~i~-th wild Pokémon's level is ~M_i~ ~(1 \le M_i \le 100\,000)~. Arbok can defeat a Pokémon if Arbok's current level is greater than or equal to that Pokémon's level. If Arbok defeats the ~i~-th wild Pokémon, Arbok's current level will increase by ~G_i~ ~(1 \le G_i \le 100\,000)~, and that Pokémon will faint and no longer occupy a point on the trail. Jessie will never make Arbok battle against a Pokémon whose level is strictly greater than Arbok's level, as Arbok would faint instead and would not be able to gain any more levels.

What's the maximum possible level which Jessie can help Arbok achieve, by optimally choosing how to walk around on the trail?

Input Specification

The first line of input consists of a single integer, ~N~.
The next line consists of two space-separated integers, ~S~ and ~L~.
~N~ lines follow, the ~i~-th of which consists of three space-separated integers, ~P_i~, ~M_i~, and ~G_i~, for ~i = 1 \dots N~.

Output Specification

Output a single integer, the maximum possible level which Arbok can achieve.

Sample Input

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

Sample Output

16

Sample Explanation

The following diagram illustrates Jessie's starting location (indicated in blue) as well as the wild Pokémon (indicated in brown):

Jessie can move left to position ~5~, and defeat the Pokémon there to increase Arbok's level to ~6~. She can then move right to position ~12~, defeating the Pokémon there and raising Arbok's level to ~14~. Finally, she can defeat the Pokémon at position ~3~ to increase Arbok's level to ~16~. This is the highest level which Arbok would ever be able to reach.