Задача N. Оптимальный план ≡

Условие

Дядя Коля стал замечать, что он не успевает делать все дела в срок. Тут ему в голову пришла идея придать планированию времени математически точную формулировку.

У дяди Коли есть N дел. Каждую минуту он может посвятить одному из них. Для каждого дела известен срок сдачи t_i, длительность выполнения дела l_i и приоритет p_i. Таким образом, на выполнение всех дел у дяди Коли уйдёт T = N∑i=1l_i минут.

Составим функционал стоимости:

∫T0C(t)dt,

C(t) = N∑i=1p_iexp [(l_i − d_i(t)) − (t_i − t)].

Здесь d_i(t) — количество времени, потраченное на i-е дело до момента времени t. В этой формуле (l_i − d_i(t)) — это сколько осталось сделать, а (t_i − t) — это сколько осталось времени до срока сдачи. В каждый момент времени t суммирование производится по номерам i, для которых d_i(t) < l_i, т.е. по не завершённым делам.

Требуется найти оптимальный план, то есть для каждой из T минут указать номер дела, которое нужно выполнить в данную минуту, чтобы функционал стоимости (интеграл) достигал наименьшего значения.

Формат входного файла

Входной файл содержит целое число N. Далее следуют N троек чисел t_i l_i p_i. Здесь t_i и l_i — целые числа, p_i — вещественное число.

Формат выходного файла

Выходной файл должен содержать минимальное значение функционала стоимости с точностью не менее 3 знаков после десятичной точки.

Ограничения

1 ≤ N ≤ 10

1 ≤ T ≤ 100

Примеры тестов

2
3 2 1
2 3 1

34.62491