Путь
Настя идёт по направлению из столовой в учебный корпус, по пути отправляя 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) - координаты отрезка пути, соответствующего очередному объекту, а также изменение температуры Насти, которое наблюдается при остановке на этом отрезке. Гарантируется, что никакие два отрезка не перекрываются.
Выходные данные
Выведите единственное целое число - минимальное итоговое изменение температуры, которое можно получить.