e-olymp
Задачі

Вчений кіт

Вчений кіт

prb49

"Край Прибережжя дуб зелений, І золотий ланцюг на нім, І день, і ніч там кіт учений - По ланцюгу кружляє тім..."

Від’їжджаючи з домівки, поет залишав коту, прикутому до дуба ланцюгом довжиною l, n рибин. Знаючи координати голови та хвоста кожної з них, порахуйте, на яку добу у кота виникне почуття голоду, якщо він починає голодувати тоді, коли за добу з'їсть менше, ніж k рибин. Рибину він може з'їсти, якщо зможе дотягнутись хоча б до однієї її точки. Координати дуба (0, 0).

Вхідні дані

У першому рядку знаходяться числа l, n, k. Далі йде n рядків: координати голови (x1i, y1i) та хвоста (x2i, y2i) кожної з рибин. Усі числа цілі, за модулем не перевищують 100.

Вихідні дані

Вивести день, на який у кота з'явиться відчуття голоду.

Ліміт часу 1 секунда
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
4 4 2
1 1 -1 3
2 2 4 2
-3 -4 -3 4
1 -5 4 -4
Вихідні дані #1
2
Автор Анатолій Присяжнюк
Джерело III етап Всеукраїнської олімпіади з інформатики в Житомирській обл. 2006-2007 р