Задание 26. Энергетические комплекты2

Задание выполняется с использованием прилагаемого файла.

На складе исследовательской станции хранятся комплекты энергетических узлов. Каждый комплект состоит из двух узлов. Для каждого узла известна его мощность — натуральное число.

Перед сборкой каждый комплект проходит проверку.

Пусть R — разность мощностей двух узлов комплекта.

• Если R < D, то комплект считается сбалансированным, и оба его узла отправляются на основную линию сборки.
• Если D ≤ R ≤ 2D, то комплект считается разделяемым: более мощный узел отправляется на основную линию сборки, а менее мощный — в резерв.
• Если R > 2D, то комплект считается нестабильным, и оба его узла отправляются в резерв.

Из узлов основной линии и из узлов резерва отдельно собирают энергетические блоки. Каждый энергетический блок состоит ровно из четырёх узлов.

Если мощности узлов блока равны x, y, z и t, где x ≤ y ≤ z ≤ t, то блок считается стабильным, если выполнены все условия:

• y − x ≥ K;
• z − y ≥ K;
• t − z ≥ K.

Энергия такого энергетического блока равна сумме произведений мощностей соседних узлов:

x·y + y·z + z·t

Каждый узел можно использовать не более чем в одном энергетическом блоке одной линии. Основная линия и резерв рассматриваются независимо.

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

Кроме того, для каждой линии отдельно рассматриваются все возможные способы выбрать четыре узла и расположить их в стабильный энергетический блок. Среди всех таких блоков для каждой линии выбирается блок с максимальной энергией.

Определите:

1. максимальное количество стабильных энергетических блоков, которое можно собрать из узлов основной линии;
2. модуль разности между максимальной возможной энергией одного стабильного энергетического блока основной линии и максимальной возможной энергией одного стабильного энергетического блока резерва.

В ответе запишите два натуральных числа: сначала количество стабильных энергетических блоков основной линии, затем найденную разность.

Входные данные

В первой строке входного файла находятся три натуральных числа:

N K D

где:

• N — количество комплектов энергетических узлов;
• K — минимальная допустимая разница мощностей соседних узлов в стабильном энергетическом блоке;
• D — порог разности мощностей узлов одного комплекта.

В следующих N строках записаны по два натуральных числа — мощности двух узлов одного комплекта.