35188번 - 고인물의 마지막 리듬게임 스페셜 저지

고인물 중 고인물. 분홍 동그라미의 마에스트로. 국가대표 주장. 수많은 단어로도 표현이 부족한 리듬게이머 카루나는 오늘도 나나미의 역작인 사운드 디제케아이아이 랩의 달인 투 온 방송을 하고 있다.

고인물 중의 고인물인 카루나가 모든 곡에서 손쉽게 퍼펙트 플레이를 달성할 수 있다는 사실은 누구나 알고 있는 사실이다. 그와 같은 고인물들을 위해, 이 게임에는 다음과 같은 하드 모드가 존재한다.

• 곡은 총 $N$개의 노트로 이루어져 있으며, 총 $M$초 동안 진행된다. 각 노트는 정해진 정수 시각 $T_i$에 버튼을 눌러 처리하여야 한다.
• 점수는 $0$점에서 시작하여, 각 노트를 성공적으로 처리하지 못할 때마다 기본 점수 $1\, 000\, 000$점을 $N$으로 나눈 만큼의 점수를 잃는다. 노트를 성공적으로 처리한다면 아무 점수도 얻지 않는다.
• 추가적으로, 각 노트에는 보너스 점수 $S_i$와 난이도 수치 $D_i$가 존재한다. 이때 $S_i<D_i$가 성립한다.
• 플레이어는 게임 시작 전에 시간 구간 $[L,R)$을 설정한다. 이때 $L$과 $R$은 정수여야 하고, $0 \le L < R \le M$ 및 $1 \le R - L \le K$가 성립해야 한다. 해당 구간 동안은 피버 타임이 발동되어, 피버 타임 내에 성공적으로 처리한 노트에 대한 $\frac{\sum S_i}{\sum D_i}$ 만큼 추가 점수를 얻는다.
• 피버 타임 내에 노트가 존재하지 않거나, 성공적으로 처리한 노트가 없다면 추가 점수를 얻지 못한다.

카루나의 방송을 즐겨보는 악질 시청자 류트는, 카루나의 게임 플레이를 방해하려고 한다. 구체적으로, 류트는 거액의 도네이션을 통해 피버 구간의 양쪽 끝 점 중 하나의 값을 $[0, M]$에 속하는 정수로 고정시킬 수 있다. 단, 고정시키는 값이 피버 구간의 시작점과 끝점 중 어느 것인지는 정할 수 없다. 그러고 난 뒤 카루나는 나머지 한 쪽 끝 점의 값을 지정한 뒤 게임을 플레이한다.

게임이 끝났을 때의 최종 점수를, 류트는 최소화하고자 하고 카루나는 최대화하고자 한다. 물론, 고인물 중의 고인물인 카루나는 자신의 점수를 최대화하기 위해서 원하는 노트만 골라서 처리하는 것이 가능하다.

방송을 보고 있는 다른 고인물 시청자인 아거스는 게임의 결과가 어떻게 될지 궁금해졌다. 아거스를 도와 최종 점수를 예측해보자.

첫 번째 줄에 노트의 개수 $N$, 곡의 길이 $M$, 피버 타임의 최대 길이 $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 각 노트에 대한 정보가 $T_i$에 대한 오름차순으로 주어진다. $i$번째 줄에는 $i$번째 노트에 대한 $T_i$, $S_i$, $D_i$가 공백으로 구분되어 주어진다.

게임이 끝났을 때의 최종 점수를 출력한다. 절대/상대 오차는 $10^{-6}$까지 허용한다.

• 주어지는 모든 수는 정수이다.
• $1\le N$, $M\le 500\, 000$
• $1\le K\le M$
• $0\le T_i<M$ ($1\le i\le N$)
• $T_{i-1}\le T_{i}$ ($2\le i\le N$)
• $1\le S_i<D_i\le 1\, 000$ ($1\le i\le N$)