Шлях
Настя йде у напрямку від їдальні до навчального корпусу, по дорозі відправляючи SMS своїм друзям у далеких містах. Відповіді приходять достатньо часто, тому не рідше, ніж на кожному k-му кроці, Насті необхідно відправити черегову SMS. Також на шляху є сонячні ділянки, кожна з яких при кожній зупинці збільшує температуру Насті на деяке число градусів, а також поливальні установки, які зменшують її температуру.
Стоїть жара, тому Настя хоче у кінці шляху мати мінімально можливу температуру. Настя хоче дійти якомога швидше, тому вона йде лише в сторону корпуса.
Вхідні дані
У першому рядку входу записано цілі числа n (1 ≤ n ≤ 1000), k (1 ≤ k ≤ x) та x (0 ≤ x ≤ 1000) - кількість об'єктів (сонячних ділянок та поливальних установок), максимальна відстань між зупинками, а також довжина шляхи Насті у кроках. У наступних n рядках записано по три цілих числа l_i, r_i (1 ≤ l_i, r_i ≤ x) та d_i (-10000 ≤ d_{i }≤ 10000) - координати відрізка шляху, який відповідає черговому об'єкту, а також зміна температури Насті, яка спостерігається при зупинці на цьому відрізку. Гарантується, що ніякі два відрізки не перекриваються.
Вихідні дані
Виведіть єдине ціле число - мінімальну результуючу зміну температури, яку можна отримати.