Російські Матрьошки
Вам, напевно, відомий знаменитий сувенір — російські матрьошки. Це набір дерев'яних ляльок, вкладених одна в одну. Менша матрьошка поміщається в більшу. Розглянемо всі матрьошки, розташовані окремо. Кожна матрьошка має зовнішній об'єм 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 — найменшу вартість, яку вам слід заплатити.