1. Коло

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

На площині задано N різних точок, жодні три з яких не лежать на одній прямій.

Завдання
Знайдіть найменший радіус кола, всередині якого і на якому разом розташовано не менше ніж K даних точок.

Вхідні дані
Перший рядок вхідного файлу містить два натуральні числа N, K при 1 ≤ K ≤ N ≤ 200.

Наступні N рядків містять по два дійсних числа, які не перевищують 1000, — координати даних точок.

Вихідні дані
Єдиний рядок вихідного файлу має містити шуканий радіус, округлений до трьох знаків після крапки, яку використовують замість десяткової коми.

Приклад

2. Канікули

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

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

Завдання
Визначте найменше ціле значення Т, за якого існує шлях селами з початком і кінцем у Києві, що принесе Петрику додатний прибуток. Існування такого шляху гарантовано вхідними даними при певному Т.

Вхідні дані
Перший рядок вхідних даних містить натуральне число N — кількість сіл (N ≤ 16). Села занумеровано натуральними числами від 1 до N. Київ має номер 0.

Кожний з наступних N + 1 рядка містять по N + 1 цілому числу — x_ij, де j — номер числа у i-му рядку у відповідній прямокутній таблиці чисел. У цій таблиці нумерацію рядків і нумерація чисел у кожному з рядків починають з нуля, 0 ≤ i, j ≤ N. Число x_ij дорівнює вартості проїзду між населеними пунктами i та j. Ці вартості не перевищують 10 000, x_ij = x_ji, x_ii = 0 при всіх i та j. Від’ємна величина x_ij вказує на відсутність прямого шляху між пунктами i та j.

Вихідні дані
Єдиний рядок вихідного файлу має містити одне ціле число — найменше ціле значення Т, за якого існує прибутковий цикл.

Приклади