Шлях#5279
Настя йде у напрямку від їдальні до навчального корпусу, по дорозі відправляючи SMS своїм друзям у далеких містах. Відповіді приходять достатньо часто, тому не рідше, ніж на кожному -му кроці, Насті необхідно відправити чергову SMS. Також на шляху є сонячні ділянки, кожна з яких при кожній зупинці збільшує температуру Насті на деяку кількість градусів, а також поливальні установки, які зменшують її температуру.
Стоїть спека, тому Настя хоче у кінці шляху мати мінімально можливу температуру. Оскільки Настя хоче дійти якомога швидше, вона йде лише у напрямку корпусу.
У першому рядку містяться три цілі числа (1 \leq n \leq 1000), (1 \leq k \leq x), і (0 \leq x \leq 1000) — кількість об'єктів (сонячні ділянки і поливальні установки), максимальна кількість кроків між зупинками та довжина шляху Насті у кроках. Кожен із наступних рядків містить три цілі числа: l_i, r_i (1 \leq l_i, r_i \leq x) і d_i (-10000 \leq d_i \leq 10000) — координати відрізка, що відповідає -му об'єкту, і зміна температури Насті, яка спостерігається при зупинці на цьому відрізку. Гарантується, що жодні два відрізки не перекриваються.
Виведіть одне ціле число — мінімально можливу підсумкову зміну температури, яку Настя може отримати по завершенні свого шляху.
Приклад 1
Приклад 2
Приклад 3