Русские Матрешки
Вам наверняка известен знаменитый сувенир Русские Матрешки. Он выглядит как множество вложенных друг в друга деревянных матрешек. Матрешка меньшего размера входит в матрешку большего. Рассмотрим все матрешки, расположенные отдельно друг от друга. Каждая матрешка имеет внешний объем out[i] - объем, который она занимает в пространстве, а также внутренний объем in[i] - объем пустого пространства, находящегося внутри ее. Будем считать, что можно положить одну матрешку в другую, если внешний объем первой строго меньше внутреннего объема второй. Если две или более матрешек находятся внутри некоторой, они не могут располагаться друг около друга, они должны быть вложены друг в друга.
Для каждой матрешки известна стоимость единицы ее свободного места cost[i]. Вам следует заплатить в точности cost[i] за каждую единицу свободного пространства, принадлежащего i-ой матрешке (но не за матрешки внутри ее). Вы можете комбинировать матрешки как угодно, лишь бы это не противоречило правилам. Задача состоит в нахождении такой комбинации вложенных матрешек (не обязательно всех имеющихся), чтобы минимизировать общую стоимость оплаты.
Входные данные
Первая строка содержит количество матрешек n (1 ≤ n ≤ 1000). i-ая из следующих n строк содержит три целых числа out[i], in[i], cost[i] (1 ≤ in[i] ≤ out[i] ≤ 1000, 1 ≤ cost[i] ≤ 1000), описывающих внешний объем, внутренний объем и стоимость пустого места i-ой матрешки.
Выходные данные
Вывести одно целое число p - наименьшую стоимость, которую Вам следует заплатить.