Problem F
Elo
Players in League of Legends play against just anyone, they can only play against others with a similar Elo score. Arnar has made a list of $n$ players, where Arnar can play against the $i$-th player only if Arnar’s Elo is in the interval $[L_ i, R_ i]$. Every time Arnar plays against the $i$-th player his Elo increases by $a_ i$, because he knows he can beat all of these players.
Arnar can play against the same player as often as he likes as long as his Elo stays in the corresponding interval.
Given the information on these $n$ players, what’s the highest Elo Arnar can achieve?
Input
The first line contains two integers $1 \le n \le 1\, 000$, the number of players and $1 \le x \le 5\, 000$, Arnar’s initial Elo score. The next $n$ lines contain three integers$1 \le L_ i \le R_ i \le 5\, 000$, $1 \le a_ i \le 500$.
Output
Print a single integer, the highest Elo Arnar can achieve.
Scoring
|
Group |
Points |
Constraints |
|
1 |
50 |
$a_ i$ is the same for all $i$ |
|
2 |
50 |
No further constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 10 15 3 10 13 2 10 11 1 |
18 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 10 10 11 5 15 16 5 20 21 30 49 49 100 |
50 |
