eolymp
bolt
Try our new interface for solving problems
Problems

The Smart Cat

The Smart Cat

Time limit 1 second
Memory limit 122.17

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).

Input data

There are L, N, K in the first line. Next N lines are as follow: coordinate of the chairman (X_{1i}, Y_{1i}) and the tail (X_{2i}, Y_{2i}) of each of the big fishes. All entrance information are integers. These numbers do not exceed 100 by the module.

Output data

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

Examples

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
2
Author Prysiazhnyuk A.