Задача C. Канатная дорога ≡

Условие

Не так давно администрация столицы Флатландии приняла решение о строительстве канатной дороги. Этот транспорт подходит городу как нельзя лучше: столица построена на N холмах, каждый из которых при взгляде сбоку имеет вид параболы с направленными вниз ветвями. То есть i-й холм можно однозначно определить такими тремя числами A_i, B_i, C_i, что точка плоскости с координатами (x, y) находится внутри холма тогда и только тогда, когда A_i x² + B_i x + C_i ≥ y. Холмы могут пересекаться, но вершина холма никогда не находится внутри другого холма.

Канатная дорога представляет собой набор из K одинаковых столбов высоты H, через вершины которых последовательно (в порядке увеличения абсциссы) протянут канат. В целях повышения надежности пассажирских перевозок столбы должны устанавливаться только на вершинах холмов. На первом и N-м холмах обязательно должны быть установлены столбы. Отрезки каната не должны пересекаться или даже касаться холмов.

Покупка уникальных столбов с античными барельефами принесла казне столицы существенные убытки, поэтому администрация хочет установить столбы так, чтобы сэкономить хотя бы на канате. Требуется написать программу, которая вычислит минимальную необходимую длину каната.

Рекомендуется рассмотреть частичные решения

• K = 2
• K = N

Формат входного файла

В первой строке входного файла находятся числа N K H, где N — количество холмов, K — число столбов и H — высота каждого из них (вещественное число). В каждой из следующих N строк содержится тройка вещественных чисел A_i B_i C_i, определяющая вид i-го холма. Холмы заданы в порядке увеличения абсциссы вершин.

Формат выходного файла

В единственную строку выходного файла выведите минимальную длину каната, необходимого для строительства, с точностью до трёх знаков после десятичной точки или −1, если построить канатную дорогу невозможно.

Ограничения

2 ≤ N ≤ 300, 2 ≤ K ≤ N, 1 ≤ H ≤ 10⁶.

−10⁶ ≤ A_i < 0, −10⁶ ≤ B_i, C_i ≤ 10⁶.

Все вещественные числа во входном файле заданы не более чем с 5 знаками после десятичной точки.

Примеры тестов

3 3 1.5
-1 -5 0
-2 0 10
-1 4 0

10.831

3 2 1.5
-1 -5 0
-2 0 10
-1 4 0

-1