Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Snowmans
Накануне Нового года ребятишки во дворе соорудили N снеговиков.
Снеговики были правильные: все – трёхкомковые, у всех диаметр
каждого следующего комка меньше диаметра предыдущего.
А утром 1 января во двор вышли Онуфрий и Елпидифор.
Они посмотрели на освещённых заходящим солнцем снеговиков и решили
соорудить своего — одного, но такого высокого, чтобы он сразу попал
в Книгу рекордов Гиннеса. Но снег, увы, не лепился…
Тогда будущие рекордсмены решили использовать комки имеющихся
снеговиков. Для устойчивости конструкции друзья решили строить
снеговика таким образом, чтобы разница между диаметрами соединяемых
комков была не меньше К и, естественно, меньший комок лежал на большем,
а не наоборот..
Вам предстоит по данным о размерах комков в каждом снеговике
определить максимальную возможную высоту снеговика Онуфрия и Елпидифора.
Входные данные. В первой строке – натуральные числа N и K,
разделённые пробелом. Далее — N строк, в каждой 3 разделённых
пробелами натуральных числа, диаметры комков снеговика, — естественно, в порядке убывания. Все числа в этой задаче не превышают 100000.
Выходные данные. Целое число, максимальная возможная высота
гиперснеговика. Будем считать что комки при стыковке не деформируются.
Для отправки решений необходимо выполнить вход.
|