15676번 - 졸업한 택희를 기리며 스페셜 저지

기나긴 학부 생활 끝에 택희는 연세대학교를 떠났다. 도현이는 위대한 택희의 업적을 기억하기 위해 동상을 세우려 한다. 도현이는 동상을 세울 후보 구역을 정했다. 도현이가 뽑은 후보 구역들은 수직선을 이루고 있다. 즉, 동상을 세울 위치는 수직선상에서의 어느 한 점이 될 것이며, 이 지점은 꼭 정수 좌표일 필요는 없다.

그러나, 동상 제작을 마칠 때쯤, 근처 야산에서 고라니들이 나타났다. N마리의 고라니들은 도현이가 동상을 세우려고 하는 수직선 위를 일정한 속도로 앞만 보고 뛰어다니며, 수직선의 맨 왼쪽에 도달하면 오른쪽으로, 맨 오른쪽에 도달한 고라니들은 왼쪽으로 방향을 바꾸며 구역을 떠나지 않고 있었다. 결국 도현이는 그냥 동상을 세우려 한다. 그러나 동상이 쓰러지면 모르고리즘 회원들에게 질타를 받기 때문에, 동상이 쓰러지지 않고 최대한 오래 버티기를 원한다.

우선 도현이는 고라니의 움직임에 대해 면밀히 조사했고, 아래와 같은 사실을 알아냈다.

• 고라니와 동상은 매우 작아 면적이 0인 점으로 표시할 수 있다.
• 각 고라니는 시작점과 보는 방향(왼쪽 또는 오른쪽)을 갖고 있으며, 보는 방향으로 1초당 거리 1을 이동하는 일정한 속도로 뛰어간다. 만약 수직선의 한쪽 끝에 도달한다면, 방향을 바꾸어 다시 일직선으로 뛰어간다. 만일 고라니끼리 마주친다면, 아무 일 없이 서로 지나쳐간다.
• 각각의 고라니는 힘 S_i를 가지고 있으며, 동상에 도달한 고라니는 그 자리에서 멈추어 동상을 영원히 민다. 이때, 동상을 왼쪽에서 미는 고라니의 힘과 오른쪽에서 미는 고라니의 힘은 서로 상쇄된다. 예를 들어, 왼쪽에서 3의 힘으로 미는 고라니와 오른쪽에서 2의 힘으로 미는 고라니가 있다면, 동상에는 오른쪽으로 1만큼의 힘만 전달된다.
• 만약 어떤 고라니의 시작점에 동상을 세운다면, 그 고라니는 뛰지 않고 바로 동상을 민다. 해당 고라니는 동상에 자기가 보는 방향으로의 힘을 가한다.
• 동상은 내구도 W를 가지고 있으며, 만약 동상에 가해지는 힘이 (어느 방향으로든) W 가 넘는다면 즉시 쓰러져버린다.
• 두 고라니가 동시에 동상을 밀기 시작한다면, 정확히 동시에 두 고라니의 힘이 전달된다. 즉, 동시에 동상에 도착하는 두 고라니가 전달하는 힘은 순서 없이 바로 합력으로 적용된다.

모르고리즘 회원들에게 욕을 듣기 싫었던 도현이는 여러분께 적절한 위치에 동상을 세웠을 때 쓰러지지 않고 서있을 수 있는 최대 시간을 계산해달라고 요청했다.

첫 줄에는 세 정수 N, T, W가 주어지며 각각 고라니의 수, 수직선 상에서의 좌표의 최댓값, 동상의 내구도를 의미한다. (1 ≤ N ≤ 7000, 1 ≤ T ≤ 10¹⁸, 0 ≤ W ≤ 10⁹)

수직선 상의 좌표의 최솟값은 항상 0이다.

두 번째 줄부터 N개의 줄에 걸쳐, i+1번째 줄마다 세 정수 P_i, D_i, S_i가 주어지며 이는 각각 고라니의 초기 위치, 방향, 그리고 고라니가 가진 힘이다. 고라니가 처음 뛰어가는 방향은 D_i = 0이라면 왼쪽, D_i = 1이라면 오른쪽이다.(0 ≤ P_i ≤ T, D_i = 0 또는 1, 0 ≤ S_i ≤ 10⁹)

고라니들의 속도는 1초당 이동거리 1로 모두 동일하다.

첫째 줄에, 적절한 위치에 동상을 세웠을 때 동상이 쓰러지지 않고 버틸 수 있는 최대 시간을 출력한다. 만약 동상이 쓰러지지 않게 세울 수 있다면 inf를 출력한다.

어떤 실수 e>0에 대해서도 x-e초에는 쓰러지지 않는 최대의 x를 최대 시간이라고 한다. 답이 inf가 아닌 경우, 정답과의 min(절대오차,상대오차)가 10^-6 이하일 경우 정답으로 인정된다.

첫 번째 예제에서 동상을 6.5의 위치에 세운다면 처음으로 3번 고라니와 4번 고라니가 동시에 동상에 도달하며 남은 힘은 3번 고라니에 의해 오른쪽에서 왼쪽으로 4만큼의 힘이 남는다. 그 다음 2번 고라니가 도달하는데, 그때 동상에 남아있는 힘은 양쪽 모두 0이 된다. 그 다음 1번 고리니가 도달하고, 이 고라니에 의해 동상이 쓰러지는데 1번 고라니가 이동한 시간은 3 + 6.5 = 9.5가 되어 답이 9.5가 된다.

두 번째 예제에서 10의 위치에 동상을 세운다면 1,2번 고라니가 동시에 도달하여 남는 힘은 오른쪽에서 왼쪽으로 4가 남는다, 그 후 3번 고라니가 왼쪽에서 오른쪽 방향으로, 4번 고라니는 오른쪽에서 왼쪽 방향으로 동시에 도달한다. 이때 왼쪽에서 오른쪽으로 작용하는 힘은 21이며, 반대 방향에는 기존에 남은 힘 4 + 7 = 13의 힘이 작용하고, 남는 힘은 왼쪽에서 오른쪽으로 8의 힘이 남는다. 이때 동상의 내구도는 10이므로 쓰러지지 않을 수 있다.