Woburn Challenge 2018-19 Round 3 - Junior Division

Problem 4: Leveling Up

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 ≤ N ≤ 1000) 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 ≤ S ≤ 100,000), while the i-th wild Pokémon's position is P_i (1 ≤ P_i ≤ 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 ≤ L ≤ 100,000), while the i-th wild Pokémon's level is M_i (1 ≤ M_i ≤ 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 ≤ G_i ≤ 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 Format

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..N.

Output Format

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.

All Submissions
Best Solutions

Point Value: 7 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Feb 01, 2019
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)