마법 유물
시간 제한2초메모리 제한512 MB
확률 p_i 위치에 유물이 하나 있는 n개 레벨을 고정 순서로 클리어해 기대 시간을 최소화한다. 레벨 i의 유물 확률이 크면 뒤로 재배치해 이득 (p_i-p_j)(a_j-b_j) 로 재정렬한다.
문제
Maxim은 비디오 게임을 하고 있다. 게임에는 1번부터 n번까지 번호가 붙은 n개의 레벨이 있다. 레벨은 어떤 순서로든 깰 수 있으며, i번째 레벨을 깨는 데 Maxim은 ai초가 걸린다.
Maxim은 레벨 중 한 곳에서 마법 유물을 찾을 수 있다. 게임에는 마법 유물이 정확히 하나 있고, 일단 찾으면 Maxim의 영웅이 빨라져 레벨을 깨는 데 걸리는 시간이 줄어든다. 하지만 유물이 어디에 있는지는 알 수 없으며, i번째 레벨에 있을 확률은 pi다. 유물을 찾은 뒤 i번째 레벨을 깨는 데 걸리는 시간은 bi초이다 (bi ≤ ai). 유물이 있는 레벨을 깨는 시간은 줄어들지 않는다.
Maxim은 게임을 깨는 데 걸리는 기댓값을 최소화하도록 레벨을 깨는 순서를 정하려 한다. 가능한 최소 기댓값을 구하자. Maxim은 게임을 시작하기 전에 레벨을 깰 순서를 정해야 하며, 그 순서는 어떤 레벨에서 유물을 찾았는지에 따라 달라져서는 안 된다.
기댓값이란 확률변수의 모든 가능한 결과에 대해 그 결과의 확률과 확률변수의 값을 곱한 것을 모두 더한 값이다. 이 문제에서 결과는 유물이 있는 레벨이고, 값은 유물이 그 레벨에 있을 때 게임을 깨는 데 걸리는 총 시간이다.
입력
입력 데이터는 여러 테스트 케이스로 이루어진다. 첫째 줄에는 테스트 케이스의 수 t가 주어진다 (1 ≤ t ≤ 1000).
각 테스트 케이스는 다음과 같다. 첫째 줄에는 레벨의 수 n이 주어진다 (1 ≤ n ≤ 105).
다음 n개의 줄에는 레벨이 주어진다. 각 레벨은 세 정수 ai, bi, xi로 주어지며, 각각 유물을 찾기 전에 그 레벨을 깨는 데 걸리는 시간, 유물을 찾은 뒤에 깨는 데 걸리는 시간, 그 레벨에서 유물을 찾을 확률을 구하는 데 쓰이는 값이다. 확률은 pi = xi / 107로 계산한다 (1 ≤ bi ≤ ai ≤ 105; 0 ≤ xi ≤ 107; 모든 xi의 합은 107).
한 입력 데이터의 모든 테스트 케이스에서 n의 합은 5·105 이하다.
출력
각 테스트 케이스마다 최적의 순서를 골랐을 때 게임을 깨는 데 걸리는 기댓값을 하나의 실수로 출력한다. 답의 절대 오차 또는 상대 오차는 10-6 이하여야 한다.