1. Шахи−2

Максимальна оцінка: 100 балів
Обмеження на час: 0,25 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: chess.in
Вихідний файл: chess.out
Програма: chess.*

Петро П’яточкін захопився грою в шахи. З метою познайомитися з грою визнаних майстрів він вирішив спостерігати всі ігри товариського матчу столичної команди проти команди села Великі Олімпійці.

Кожен гравець має певний рівень гри, який подають натуральним числом. Два гравці можуть грати між собою, якщо вони з різних команд та їхній рівень гри відрізняється не більше ніж на d — певне невід’ємне ціле число. У кожній грі беруть участь по шахістові з кожної команди, які можуть грати між собою. Причому кожен гравець може грати не більше ніж у одній грі.

Петрику кортить побувати на якомога більшій кількості зустрічей. Тому він попрохав знайомого чарівника втрутитися: змінити рівень гри усім гравцям сільської команди на одну й ту саму кількість одиниць (ціле число) таким чином, щоб максимально збільшити кількість можливих ігор. Зауважимо, що після втручання чарівника рівні деяких гравців можуть стати від’ємними.

Завдання
Знаючи рівні гри усіх гравців і d, вкажіть:

• на яку величину потрібно змінити рівень гри сільських гравців так, щоб було зіграно найбільшу кількість ігор;

• як поєднати гравців команд-суперників у пари, щоб провести цю найбільшу кількість ігор (потрібно вказати лише один варіант такого поєднання).

Вхідні дані
Перший рядок вхідного файлу містить 3 цілих числа:
N — кількість гравців сільської команди (1 ≤ N ≤ 200);
M — кількість гравців столичної команди (1 ≤ M ≤ 200);
d — верхня межа різниці рівнів гравців, які можуть зіграти партію (0 ≤ d ≤ 10⁹).

Усі наступні числа натуральні і не перевищують 10⁹.
Другий рядок містить N чисел — рівні гравців сільської команди.
Третій рядок містить M чисел — рівні гравців столичної команди.

Вихідні дані
Перший рядок вихідного файлу має містити два цілих числа: K — максимально можливу кількість ігор після відповідного втручання чарівника (навіть якщо він нічого не змінював) і D — величину, на яку треба змінити рівень гри сільських гравців, так щоб було зіграно K ігор.

Наступні K рядків мають містити K різних пар натуральних чисел по одній у кожному рядку. Кожна пара — це номер гравця сільської команди і номер гравця столичної команди, відповідно, які мають зіграти між собою партію, щоб загалом було зіграно K партій. Пари можна виводити у будь-якому порядку.

Приклади

2. Сервери

Максимальна оцінка: 100 балів
Обмеження на час: 0,5 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: servers.in
Вихідний файл: servers.out
Програма: servers.*

Корпорація має N серверів, які занумеровано натуральними числами від 1 до N. Кожен сервер займає одну полицю в серверній стійці. Всього у стійці N полиць, і їх також занумеровано натуральними числами від 1 до N. У зв’язку з заміною обладнання виникла потреба переставити сервери. Проблему ускладнено тим, що деякі пари серверів потрібно з’єднати кабелем напрямý. Довжина кабелю, що з’єднує пару серверів, дорівнює різниці номерів полиць, на яких розташовані ці сервери. Допоможіть розмістити сервери так, щоб сумарна довжина затраченого кабелю була найменшою.

Завдання
Визначте, яку найменшу сумарну довжину кабелю потрібно витратити для розташування серверів у серверній стійці та одне з можливих таких розташувань.

Вхідні дані
Перший рядок вхідного файлу містить натуральне число N (2 ≤ N ≤ 20).

Другий рядок вхідного файлу містить ціле число M — кількість пар серверів, що потрібно з’єднати напрямý.

Наступні M рядків містять по одній парі різних натуральних чисел — номери серверів, що потрібно з’єднати напрямý. Кожна така пара зустрічається у переліку лише один раз.

Вихідні дані

Перший рядок вихідного файлу повинен містити єдине число — найменшу можливу сумарну довжину кабелю.

Другий рядок вихідного файлу повинен містити перестановку чисел 1, 2, …, N, що відповідає оптимальному розташуванню серверів: на j-му місці має стояти номер сервера, який потрібно встановити на j-ту полицю.

Приклад