eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кот учёный

Кот учёный

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной l, n рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем k рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба (0, 0).

Входные данные

В первой строке находятся числа l, n, k. Далее идет n строк: координаты головы (x[1i], y[1i]) и хвоста (x[2i], y[2i]) каждой рыбины. Все входные данные - целые числа, не превышающие по модулю 100.

Выходные данные

Вывести день, на который у кота появится чувство голода.

Пример

Входные данные #1
4 4 2
1 1 -1 3
2 2 4 2
-3 -4 -3 4
1 -5 4 -4
Выходные данные #1
2