Вам наверняка известен знаменитый сувенир Русские Матрешки. Он выглядит как множество вложенных друг в друга деревянных матрешек. Матрешка меньшего размера входит в матрешку большего. Рассмотрим все матрешки, расположенные отдельно друг от друга. Каждая матрешка имеет внешний объем outi - объем, который она занимает в пространстве, а также внутренний объем ini - объем пустого пространства, находящегося внутри ее. Будем считать, что можно положить одну матрешку в другую, если внешний объем первой строго меньше внутреннего объема второй. Если две или более матрешек находятся внутри некоторой, они не могут располагаться друг около друга, они должны быть вложены друг в друга.

Для каждой матрешки известна стоимость единицы ее свободного места costi. Вам следует заплатить в точности costi за каждую единицу свободного пространства, принадлежащего i-ой матрешке (но не за матрешки внутри ее). Вы можете комбинировать матрешки как угодно, лишь бы это не противоречило правилам. Задача состоит в нахождении такой комбинации вложенных матрешек (не обязательно всех имеющихся), чтобы минимизировать общую стоимость оплаты.

Входные данные

Первая строка содержит количество матрешек n (1 ≤ n ≤ 1000). i-ая из следующих n строк содержит три целых числа outi, ini, costi (1 ≤ ini ≤ outi ≤ 1000, 1 ≤ costi ≤ 1000), описывающих внешний объем, внутренний объем и стоимость пустого места i-ой матрешки.

Выходные данные

Вывести одно целое число p - наименьшую стоимость, которую Вам следует заплатить.