Задача Санная трасса

Описание

Как известно, к северу от Москвы находится много горнолыжных трасс, расположенных на холмах Клинско-Дмитровской гряды. Один из курортов в связи с финансовым кризисом решил расширить спектр услуг, предлагая трассы для катания не только на лыжах и сноубордах, но и санные трассы.

У хозяев курорта имеется топографическая карта территории, высоты на которой отображены с помощью контуров, каждый из которых представляет собой окружность. У каждой окружности указана высота поверхности, прилегающей к внутреннему контуру этой окружности. Вся территория, которая не находится внутри какой-либо окружности, имеет высоту 0. Поскольку это единственная информация о местности, то можно условно считать, что участки между окружностями плоские. Никакие две окружности не пересекаются и не касаются.

Используя эту карту, необходимо проложить санную трассу, которая будет удовлетворять двум условиям: разница высот между начальной и конечной точками должна быть максимальна, и количество пересекаемых контуров не должно превышать некоторого заданного значения K (это связано с тем, что то место, которым сидят на санках, имеет ограниченную прочность). При этом трасса может иметь участки подъема, но не должна включать в себя ни одной точки, которая была бы выше начальной (туда санки просто не заедут).

На приведенном рисунке пунктирной линией показана наилучшая трасса для K = 4. Разница высот в ней составляет 68.

Формат входных данных

Сначала вводятся два натуральных числа C (1 ≤ C ≤ 2 000) — количество окружностей и K (1 ≤ K ≤ 2 000) – максимальное количество окружностей, которое может пересечь трасса.

Далее идут описания окружностей, каждое из которых состоит из четырех целых чисел: X, Y (–2000 ≤ X ≤ 2000, –2000 ≤ Y ≤ 2000) – координаты центра окружности, R (1 ≤ R ≤ 2000) — радиус окружности и A (–1000 ≤ A ≤ 1000) — высота местности, касающейся внутреннего края окружности.

Формат выходных данных

Выведите одно число — максимальный перепад высот на трассе.