정치의 불확실성

워싱턴 D.C. 여행을 앞두고 의회 위원회 청문회를 최대한 많이 방청하려 한다. 지역구 의원이 어떤 청문회든 방청석에 들어갈 수 있는 출입증을 마련해 주었다. 다만 일정을 짜는 데 걸림돌이 세 가지 있다.

1. 위원회가 많은 만큼 청문회도 많고, 시간이 겹치는 청문회도 있다.
2. 위원회는 시작 시각을 정확히 지키지만, 청문회가 얼마나 이어질지는 예측하기 어렵다. 위원회 청문회에서는 의사 진행 방해가 허용되지 않으므로 청문회가 영원히 이어지지는 않는다.
3. 이미 시작한 청문회에 들어가거나 끝나기 전에 나오는 것은 결례다. 출입증을 마련해 준 의원이 곤란해지지 않도록, 방청하기로 한 청문회는 처음부터 끝까지 자리를 지켜야 한다. 청문회장은 서로 가까워서, 한 청문회가 끝나는 즉시 그 시각에 시작하는 다른 청문회로 옮겨 갈 수 있다.

의회는 여행 한참 전에 청문회 일정을 공개한다. 청문회마다 시작 시각 $s$와 진행 시간의 최솟값 $a$, 최댓값 $b$를 알려 준다. 실제 진행 시간은 닫힌 구간 $[a, b]$의 정수 중 하나가 균등한 확률로 정해진 값이다. 즉 청문회는 시각 $s$에 시작해 시각 $s + L$에 끝나고, $L$은 $a \le L \le b$인 정수 중 하나가 모두 같은 확률로 정해진다.

방청하는 청문회 수의 기댓값을 최대로 만드는 전략을 찾아야 한다. 예를 들어 청문회가 네 개이고 값이 다음과 같다고 하자.

이 일정에서 최적 전략의 기댓값은 2.125다. 먼저 시각 3에 시작하는 NASA 청문회를 방청한다. 진행 시간이 집합 {2, 3}에서 균등하게 정해지므로 이 청문회는 시각 5나 시각 6에 같은 확률로 끝난다. 시각 5에 끝나면 곧바로 석유와 가스 시추 청문회로 옮겨 가고, 그 청문회가 시각 6에 끝날 확률이 1/4이므로 그때는 허리케인 복구 청문회까지 세 번째로 방청한다. NASA 청문회가 시각 6에 끝나면 바로 허리케인 복구 청문회로 간다. 이 전략이면 12.5% 확률로 세 번, 나머지 87.5% 확률로 두 번 방청하므로 기댓값이 2.125다. 소셜 미디어와 선거 청문회부터 방청하면 운이 좋을 때 네 번까지 방청하지만, 그 청문회로 시작할 때의 최적 기댓값은 2.10714에 그친다.

첫 줄에 예정된 청문회의 수 $n$이 주어진다 ($1 \le n \le 10^4$). 이어지는 $n$개 줄에는 청문회 하나의 시작 시각 $s$, 최소 진행 시간 $a$, 최대 진행 시간 $b$가 공백으로 구분되어 주어진다 ($1 \le s \le 10^6$, $1 \le a \le b \le 10^6$). 청문회는 시작 시각이 감소하지 않는 순서로 나열된다.

최적 전략으로 방청하는 청문회 수의 기댓값을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래는 항상 여섯 자리를 채운다. 값이 1이면 1.000000으로 출력한다. 모든 테스트 데이터에서 정답은 반올림 경계에 걸리지 않으므로 반올림 방향은 문제가 되지 않는다.