№221540514
Для выставки нужно отобрать экспонаты, стоящие в зале в фиксированном порядке. У каждого экспоната есть целочисленная оценка зрелищности. Соседние выбранные экспонаты (не обязательно стоящие рядом в зале) должны отличаться по оценке не меньше чем на D: модуль разности оценок не меньше D. Пропускать экспонаты можно, менять их порядок нельзя. Допустима подборка даже из одного экспоната.
Определите наибольшую возможную сумму оценок экспонатов в такой подборке.
Входные данные
В первой строке входного файла записаны два натуральных числа N и D - количество экспонатов и минимально допустимая разность соседних выбранных оценок (N не превышает 10 000, D не превышает 1000). Во второй строке записаны N натуральных чисел - оценки экспонатов в порядке их расположения (каждое число не превышает 1 000 000).
В ответе запишите одно целое число - максимальную сумму оценок.
Типовой пример организации данных во входном файле
6 3 3 1 4 2 8 5
При D = 3 одна из подборок с наибольшей суммой даёт 18. Ответ для примера: 18.
Типовой пример имеет иллюстративный характер. Чтобы выполнить это задание, используйте данные из прилагаемого файла.