Кот учёный

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

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

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

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

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

Примеры