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

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

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

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

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

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

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

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

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

Энергия такого энергоблока равна:

x·y + y·z

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

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

Определите:

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

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

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

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

N K D

где:

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

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

Пример входного файла

10 5 4
10 13
20 27
30 36
40 43
50 60
22 24
70 82
15 25
33 34
45 52

После проверки комплектов на основную линию попадут узлы:

10 13 24 22 43 40 34 33 27 36 52

В резерв попадут узлы:

20 30 50 60 70 82 15 25 45

Для основной линии можно собрать 3 стабильных энергоблока с максимальной суммарной энергией:

24 34 40
33 43 52
10 22 27

Их суммарная энергия равна:

24·34 + 34·40 + 33·43 + 43·52 + 10·22 + 22·27 = 6631

Для резерва можно собрать 2 стабильных энергоблока с максимальной суммарной энергией:

50 60 82
15 25 30

Их суммарная энергия равна:

50·60 + 60·82 + 15·25 + 25·30 = 9045

Модуль разности:

9045 − 6631 = 2414

Ответ для примера:

3 2414