Завдання № 23
відбірково-тренувальних зборів
команди міста Києва


за матеріалами ІІІ (міського) етапу 2008 року

1. Коло

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


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

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

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

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

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

Приклад

circle.incircle.out
3 3
0.0 1.0
-1.0 -1.0
1.0 -1.0
1.250



2. Канікули

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


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

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

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

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

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

Приклади

vacation.invacation.out
2
0 2 2
2 0 1
2 1 0
3



2
0 2 2
2 0 -1
2 -1 0
5