시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 3 | 2 | 2 | 66.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 10 4 8 6
4
We start with F = 4 litres of fuel and
This is the minimum F possible.
5 100 50 30 25 50 40 25 25 25 25 75 20 25 5 5 25
20
We start with F = 20 litres of fuel and
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.