Майже все Королівство Байтленд вкрито лісами та ріками. Малі ріки зливаються в крупніші ріки, які, у свою чергу, зливаються одна з одною; наприкінці, всі річки зливаються разом в одну велику ріку. Велика ріка впадає в море поблизу міста Байттаун. В Байтленді є \textbf{n} лісозаготівельних селищ, кожне з яких розташоване поблизу будь-якої ріки. На сьогодні в Байттауні знаходиться велика пилорама, яка опрацьовує всі дерева, зрублені в Королівстві. Дерева сплавляються вниз по рікам від селищ, де вони зрубані, до пилорами в Байттауні. Король Байтленду вирішив поставити \textbf{k} додаткових пилорам в селищах, щоб зменшити вартість сплаву дерев. Після установки пилорам дерева не обов'язково повинні сплавлятися в Байттаун, тепер їх можна обробити на найближчій пилорамі, що знаходиться нижче за течією рік. Очевидно, що дерева, зрублені в околиці селища з пилорамою, взагалі не сплавляються по рікам. Необхідно відмітити, що ріки в Байтленді не розгалужуються. З цього слідує, що для кожного селища існує єдиний шлях сплаву дерев вниз за течією рік від нього в Байттаун. Королівські рахувальники підрахували кількість дерев, що зрубуються в кожному селищі за рік. Вам необхідно визначити, у яких селищах потрібно встановити пилорами, щоб мінімизувати сумарну вартість сплаву дерев за рік. Вартість сплаву одного дерева коштує один цент за кожен кілометр шляху. Напишіт програму, яка: \begin{itemize} \item читає зі стандартного вводу кількість селищ, кількість додаткових пилорам, які будуть встановлені, кількість зрублених в кожному селищі дерев та опис рік, \item обчислює мінімальну вартість сплаву дерев після встановлення додаткових пилорам, \item виводить результат у стандарний вивід. \end{itemize} \InputFile Перший рядок вхідних даних містить два цілих числа: \textbf{n} --- кількість селищ, не рахуючи Байттауна (\textbf{2 }≤ \textbf{n} ≤ \textbf{100}), та \textbf{k} --- кількість додаткових пилорам, які будуть встановлені (\textbf{1} ≤ \textbf{k} ≤ \textbf{50} и \textbf{k} ≤ \textbf{n} ). Селища нумеруються числами \textbf{1}, \textbf{2}, ..., \textbf{n}, а Байттаун має номер \textbf{0}. Кожен з наступних \textbf{n} рядків містить три цілих числа, відокремлених одним пропуском. Рядок \textbf{i+1} містить: \begin{itemize} \item \textbf{w_i} --- кількість дерев, що зрубуються у селищі \textbf{i} за рік (\textbf{0} ≤ \textbf{w_i} ≤ \textbf{10000}), \item \textbf{v_i} --- найближче селище (або Байттаун) вниз по річці від селища \textbf{i} (\textbf{0} ≤ \textbf{v_i} ≤ \textbf{n} ), \item \textbf{d_i} --- відстань (в кілометрах) по річці від селища \textbf{i} до селища \textbf{v_i} (\textbf{1} ≤ \textbf{d_i} ≤ \textbf{10000}). \end{itemize} Гарантиується, що сумарна вартість сплаву всіх дерев до пилорами в Байттауні не перевищує \textbf{2000000000} центів за рік. \OutputFile Перший і єдиний рядок вихідних даних повинен містити одне ціле число: мінімальну вартість сплаву (в центах). \includegraphics{https://static.e-olymp.com/content/10/10b141f690b9cc741a5542443d77e7d08da77eee.jpg} Рисунок зверху илюструє вхідні дані приклада. Номери селищ вказані всередині кругів. Числа під кругами позначають кількість дерев, що зрубуються поблизу цього селища. Числа над стрілками вказують довжини рік. Пилорами поіинні бути встановлені у селищах \textbf{2} та \textbf{3}.