시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB32266.667%

문제

As oil prices plummet, Pengu the Penguin has decided to visit Squeaky the Mouse who lives D kilometres away.

Pengu’s spheniscidae-mobile starts its journey with F litres of fuel, consumes 1 litre of fuel per kilometre, and is able to hold any amount of fuel at any point in time.

Furthermore, there are N fuel stations between Pengu and his destination, with the ith fuel station being Xi kilometres away from Pengu’s house. At each fuel station, Pengu is only able to top up Ai litres of fuel (a limit imposed to prevent drivers from hoarding cheap fuel), and only if F ≤ Bi (to ensure that the fuel goes to drivers who most need it), Here, F refers to the amount of fuel (in litres) that Pengu started with.

Being an efficient penguin, Pengu would like to minimise the value of F while still being able to reach his destination.

입력

Your program must read from standard input. The first line contains two integers N and D. N lines will follow. The ith line contains three integers Xi, Ai and Bi, which represent the ith fuel station.

출력

Your program must print to standard output. The output should contain a single integer on a single line, the minimum value of F needed to reach the destination.

제한

  • 1 ≤ N ≤ 3 × 105
  • 1 ≤ Ai, Bi, D ≤ 109
  • 0 < Xi < D

예제 입력 1

1 10
4 8 6

예제 출력 1

4

We start with F = 4 litres of fuel and

  1. Reach the only fuel station (X1 = 4) with 4 − 4 = 0 litres of fuel left.
  2. Top up A1 = 8 litres of fuel since F ≤ B1 = 6 to obtain 0 + 8 = 8 litres of fuel left.
  3. Reach our destination at X = 10 with 8 − (10 − 4) = 2 litres of fuel left.

This is the minimum F possible.

예제 입력 2

5 100
50 30 25
50 40 25
25 25 25
75 20 25
5 5 25

예제 출력 2

20

We start with F = 20 litres of fuel and

  1. Reach the 5th fuel station (X5 = 5) with 20 − 5 = 15 litres of fuel left.
  2. Top up A5 = 5 litres of fuel since F ≤ B5 = 25 to obtain 15 + 5 = 20 litres of fuel left.
  3. Reach the 3rd fuel station (X3 = 25) with 20 − (25 − 5) = 0 litres of fuel left.
  4. Top up A3 = 25 litres of fuel since F ≤ B3 = 25 to obtain 0 + 25 = 25 litres of fuel left.
  5. Reach the 1st and 2nd fuel stations (X1 = X2 = 50) with 25−(50−25) = 0 litres of fuel left.
  6. Top up A1 + A2 = 70 litres of fuel since F ≤ B1 = B2 = 25 to obtain 0 + 70 = 70 litres of fuel left.
  7. Reach our destination at X = 100 with 70 − (100 − 50) = 20 litres of fuel left.

This is the minimum F possible.

Note that we could have also used the 4th fuel station (X4 = 75) if we wanted to. Although we reach it with 70 − (75 − 50) = 45 ≰ B4 = 25 litres of fuel left, we can still use it since F = 20 ≤ B4 = 25. However, we are still able to reach our destination even if we do not use the fuel station.