Gift#5278
On August 14, the world celebrates two special occasions: the International Team Programming Olympiad among parallels A, A′, and B, and World Girls' Day at LKS. To mark this day, the senior students decided to gift their campmates by providing unlimited Wi-Fi to every house. The houses at LKS are rectangular, with sides parallel to the coordinate axes; none of them intersect the axis (i.e., the line y = 0).
After successful negotiations with the local provider, the students managed to secure several routers and receivers. However, the provider stipulated that all routers must be placed near the nearest road, which conveniently runs along the line y = 0. Routers must be connected to their neighbors along this line by cables, and to minimize interference, all cables must have length at most .
One router receives the internet from the provider and relays it by cable to the others. Each router can broadcast wireless internet within a radius of . For a house to have internet access, a receiver must be placed at a point inside the house so that it is within the broadcast radius of at least one router. A single router can serve any number of receivers.
Since nearly all the students’ money was spent on cola and cookies, they wish to minimize the number of routers rented (receivers are provided free of charge). Help them determine the minimum number of routers required.
The first line contains three integers: 1 \leq N \leq 100\,000 — the number of houses; and 1 \leq dv, dh \leq 100\,000 — the broadcast radius of a router and the maximum allowed cable length. Each of the next lines contains four integers x_1, y_1, x_2, y_2, where x_1 < x_2 and y_1 < y_2, describing a single house as a rectangle with opposite corners at (x_1, y_1) and (x_2, y_2). The absolute values of all coordinates do not exceed . All numbers in the input are integers.
Output the minimum number of routers required, or -1 if no solution exists.
Example 1