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

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

В первой строке находятся числа l, n, k. Далее идет n строк: координаты головы (x1i, y1i) и хвоста (x2i, y2i) каждой рыбины. Все входные данные - целые числа, не превышающие по модулю 100.

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

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