The Smart Cat

The Smart Cat


"On seashore far a green oak towers,
And to it with a gold chain bound,
A learned cat whiles away the hours
By walking slowly round and round..."

When the poet went out from the house he left for a cat N big fishes. The cat was chained up to oak. The length of chain was L. You have to calculate the quantity of day when the cat will senses the hunger. You know the coordinate of the chairman and the tail of each of the big fish. The cat will senses the hunger when he will eat less than K big fishes on the day. He can eat big fish if he can touch to one of its point. The coordinates of the oak is (0, 0).


There are L, N, K in the first line. Farther N lines goe: coordinate of the chairman (X1i, Y1i) and the tail (X2i, Y2i) of each of the big fishes. All entrance information are integers. These numbers do not exceed 100 by the module.


There is a one number - a day on which cat will senses the hunger in the file.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
4 4 2
1 1 -1 3
2 2 4 2
-3 -4 -3 4
1 -5 4 -4
Output example #1
Author Prysiazhnyuk A.