Розподіл Землі
Король далекого королівства помер, і тепер його володіння мають бути поділені між K синами. Королівство, яке можна уявити у вигляді прямокутної карти, складається з N міст. Щоб розділити цю територію, сини проведуть K-1 прямих ліній на карті, які будуть паралельні або вертикальній, або горизонтальній осі. Це розділить карту на рівно K прямокутників, кожен з яких матиме однакову висоту (якщо лінії поділу вертикальні) або однакову ширину (якщо лінії поділу горизонтальні). Жодна з цих ліній не повинна проходити через жодне місто. Кожен син отримає один з K регіонів, і міста в цьому регіоні стануть його часткою.
Звісно, вони прагнуть до максимально справедливого поділу: ідеально, кожен син повинен отримати N/K міст (це значення ми назвемо базовим), але оскільки базове значення не завжди є цілим числом, кожен з синів хоче бути якомога ближче до цього значення. Несправедливість для кожного сина визначається як абсолютна різниця між кількістю міст, які йому дісталися, і базовим значенням. Найсправедливіший поділ - це той, що мінімізує середню несправедливість усіх синів.
Розглянемо приклад вище з 3 синами і 6 містами (тому базове значення 6/3 = 2.0). Фігура (a) - це оригінальна карта. Фігура (b) показує неоптимальний поділ (пунктирні лінії - це 2 лінії поділу). У цьому випадку середній регіон містить 3 міста (несправедливість |3 - 2| = 1), лівий регіон містить 1 місто (несправедливість |1 - 2| = 1), тоді як правий регіон містить 2 міста (ідеально справедливо, несправедливість 0), тому середня несправедливість становить 2/3.
Фігура (c) праворуч показує оптимальний поділ, оскільки всі три регіони містять однакову кількість міст, що дає середню несправедливість 0.
Напишіть програму, щоб визначити найсправедливіший поділ землі для даного королівства.
Вхідні дані
Ваша програма буде протестована на одному або більше тестових випадках. Кожен тестовий випадок описується на N+1 рядках.
Перший рядок кожного тестового випадку містить два додатні цілі числа: (N ≤ 100, 000) і (K ≤ 10), де N - це кількість міст, а K - кількість дітей. Зверніть увагу, що K ≤ N.
Далі йде N рядків, кожен з яких описує координати міста, вказуючи два цілі числа (x, y), де 0 ≤ x, y ≤ 100, 000. Оскільки координати округлені до найближчого цілого числа, більше ніж одне місто може мати однакові координати на карті. Ви можете припустити, що карта королівства - це будь-який прямокутник, що містить усі задані точки (хоча така інформація не потрібна програмі). Зверніть увагу, що хоча всі міста лежать на цілих координатах, лінії поділу не обов'язково повинні бути.
Останній рядок вхідного файлу містить два нулі.
Вихідні дані
Для кожного тестового випадку надрукуйте наступний рядок:
k. A/B
Де k - номер тестового випадку (починаючи з одного), а A/B - це мінімальне середнє, яке можна отримати. A/B повинно бути нескоротним дробом. Нехай B=1, коли результат є цілим числом.
Примітка: Перед A є пробіл.