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