물탱크
시간 제한8초메모리 제한512 MB
매일 반복되는 물 사용 일정이 주어질 때, 탱크가 바닥나지 않게 하는 최소 펌프 속도를 구한다.
문제
아파트를 지으면서 주민이 쓸 물을 담아 두는 용량 짜리 물탱크를 설치했다. 이 탱크는 수도 회사와 주민 사이에서 완충 장치가 된다.
물을 쓰는 동안 물이 모자라면 안 된다. 탱크에는 펌프로 물을 채운다. 펌프가 강할수록 물이 모자랄 걱정은 줄지만, 강한 펌프는 비싸다. 그래서 조건을 만족하는 가장 약한 펌프의 성능을 알아야 한다.
하루 물 사용 일정표는 매일 똑같다. 일정표는 여러 개의 일정으로 이루어지고, 각 일정은 사용 시작 시각, 사용 종료 시각, 그 구간에서 단위 시간당 쓰는 물의 양으로 정해진다.
일정표를 보고 펌프가 물을 넣어야 하는 최소 속도를 구하는 프로그램을 작성하라.
다음 조건이 성립한다.
- 하루는 86400단위 시간이다.
- 시각 0보다 먼저 시작하는 일정은 없고, 시각 86400보다 늦게 끝나는 일정도 없다.
- 두 일정은 서로 겹치지 않는다.
- 일정이 없는 동안에는 물을 쓰지 않는다.
- 펌프는 하루 종일 멈추지 않고 일정한 속도 로 물을 넣는다. 는 음이 아닌 실수다.
- 저장된 물의 양이 용량 을 넘으면 넘친 만큼은 흘러 나가므로, 저장량은 항상 이하다.
- 탱크는 첫째 날 시각 0에 가득 차 있다.
시각 의 저장량을 라고 하면 모든 시각에서 이어야 한다. 일정표는 매일 같은 형태로 끝없이 반복되고, 이 조건은 모든 날에 대해 성립해야 한다. 이를 만족하는 가장 작은 를 구하라.
입력
입력은 여러 개의 데이터 집합으로 이루어진다. 각 데이터 집합은 일정표 하나를 나타내며, 형식은 다음과 같다.
N L
s1 t1 u1
...
sN tN uN
첫 줄에는 정수 과 이 주어진다 (, ). 은 일정의 개수이고 은 탱크의 용량이다.
이어지는 개의 줄 중 번째 줄에는 번 일정을 나타내는 세 정수 , , 가 주어진다. 와 는 사용 시작 시각과 종료 시각이고, 는 그 구간에서 단위 시간당 쓰는 물의 양이다 (). 시각은 을 만족한다.
입력의 끝에는 0이 두 개 있는 줄이 오고, 이 줄은 처리하지 않는다.
한 입력에 들어 있는 데이터 집합은 20개 이하이고, 모든 데이터 집합의 을 더한 값은 100000 이하다.
출력
각 데이터 집합마다 펌프가 넣어야 하는 단위 시간당 최소 물의 양을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래 자릿수는 정확히 여섯 자리여야 한다.
정답은 항상 이하다. 정답이 소수점 아래 여섯째 자리 반올림의 경계값에서 이내로 가까운 경우는 없으므로, 출력할 값은 하나로 정해진다.