Задачі
Вчений кіт
Вчений кіт
Від’їжджаючи з домівки, поет залишав коту, прикутому до дуба ланцюгом довжиною l, n рибин. Знаючи координати голови та хвоста кожної з них, порахуйте, на яку добу у кота виникне почуття голоду, якщо він починає голодувати тоді, коли за добу з'їсть менше, ніж k рибин. Рибину він може з'їсти, якщо зможе дотягнутись хоча б до однієї її точки. Координати дуба (0, 0).
Вхідні дані
У першому рядку знаходяться числа l, n, k. Далі йде n рядків: координати голови (x1i
, y1i
) та хвоста (x2i
, y2i
) кожної з рибин. Усі числа цілі, за модулем не перевищують 100.
Вихідні дані
Вивести день, на який у кота з'явиться відчуття голоду.
Вхідні дані #1
4 4 2 1 1 -1 3 2 2 4 2 -3 -4 -3 4 1 -5 4 -4
Вихідні дані #1
2