Вчений кіт

Від’їжджаючи з домівки, поет залишав коту, прикутому до дуба ланцюгом довжиною l, n рибин. Знаючи координати голови та хвоста кожної з них, порахуйте, на яку добу у кота виникне почуття голоду, якщо він починає голодувати тоді, коли за добу з'їсть менше, ніж k рибин. Рибину він може з'їсти, якщо зможе дотягнутись хоча б до однієї її точки. Координати дуба (0, 0).

Вхідні дані

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

Вихідні дані

Вивести день, на який у кота з'явиться відчуття голоду.

Приклади