e-olymp
Задачи

Кот учёный

Кот учёный

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной 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