Артеміда#2124
Зевс, бог неба, виділив Артеміді (богині дикої природи) прямокутну ділянку для вирощування лісу. Ліва сторона ділянки прилягає до додатної частини осі , нижня — до додатної частини осі , а точка є лівим нижнім кутом цієї території. Зевс наказав Артеміді саджати дерева лише у точках з цілими координатами. Щоб ліс виглядав природно, Артеміда розташувала дерева так, що відрізок, який сполучає будь-які два дерева, ніколи не буде паралельним осям або .
Одного дня Зевс попросив Артеміду зрубати деякі дерева, дотримуючись наступних правил:
Необхідно зрубати принаймні дерев.
Щоб створити прямокутний футбольний майданчик, Артеміда має зрубати усі дерева, що знаходяться всередині певної прямокутної області, і жодного поза її межами.
Сторони цієї прямокутної області мають бути паралельні осям та .
Два протилежних кути цієї області мають співпадати з розташуванням дерев, і ці дерева також потрібно зрубати.
Оскільки Артеміда дуже любить свої дерева, вона хоче виконати цю вимогу, зрубавши якомога менше дерев. Ваше завдання — написати програму, яка за заданими координатами дерев і мінімальною кількістю дерев для зрубання, обере площу для вирубки.
Перший рядок містить одне ціле число — кількість дерев. Другий рядок містить одне ціле число — мінімальну кількість дерев для зрубання. Наступні рядків описують координати дерев. У кожному рядку задано два цілих числа: та — -координата та -координата дерева.
Для всіх випадків: 1 < N \leq 20000, 0 \leq X, Y \leq 64000, 1 < T \leq N. У випадків: 1 < N < 5000.
Виведіть у єдиному рядку два цілих числа і , розділені пробілом. Артеміда має розглядати дерево з рядка (I+2) та дерево з рядка (J+2) вхідного файлу як кути прямокутника для вирубки дерев. Порядок і у відповіді не має значення. Якщо існує кілька допустимих пар, ви можете вивести будь-яку. Для всіх тестових випадків гарантовано існування хоча б одного розв'язку.
Приклад 1