H. Hathsin's piths
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Kelsier has been trapped inside the deadly pits of Hathsin. He was sure he would die inside, but he had awakened his allomantic powers and could try to escape now! His powers allow him, among other things, to pull himself towards or push himself from metal rods, and he plans to use them to their full potential.

The pits can be seen as a 2D plane that goes from $$$0$$$ to $$$-\inf$$$ in the Y axis, and from $$$-\inf$$$ to $$$\inf$$$ in the $$$X$$$ axis. The wall is full of ledges, some of which have metal rods. Kelsier can pull himself into any metal rod that's at most $$$k$$$ units away, and can push himself from any ledge with a metal rod to another ledge that's at most $$$h$$$ units away or to the surface if it's at most $$$h$$$ units away. Kelsier will have escaped if he reaches the surface, which is represented as an infinite line from $$$(-\inf,0)$$$ to $$$(\inf,0)$$$

Given the position of the ledges and whether they have metal rods or not, help Kelsier find the minimum number of pulls and pushes he will have to do to escape.

Input

On the first line, 3 integers $$$N,h,k$$$ ($$$1\leq N \leq 10^4, 1\leq h,k \leq 10^9$$$) representing the number of ledges, how far away Kelsier can push himself, and how far he can pull himself, respectively.

On the next $$$N$$$ lines, 3 integers, $$$x_i, y_i, z_i$$$ ($$$-10^9\leq x_i \leq 10^9, -10^9\leq y_i \leq 0$$$, $$$z_i\in \{0,1\}$$$). The first two numbers indicate that there is a ledge in $$$(x_i,y_i)$$$, and $$$z_i$$$ will be $$$1$$$ if the ledge has a metal rod, or $$$0$$$ otherwise.

In the last line, 2 integers $$$a,b$$$ ($$$-10^9\leq a \leq 10^9, -10^9\leq b \leq 0$$$) indicating that Kelsier starts in position($$$a,b$$$). There will always be a ledge in the starting coordinates.

Output

Just a number $$$m$$$, the minimum number of pushes and pulls Kelsier has to do to escape. If there is no way to escape, print $$$-1$$$

Examples
Input
5 1 3
1 -3 0
2 -2 0
-2 -3 1
0 -1 1
-1 -2 0
1 -3
Output
2
Input
5 1 3
1 -3 0
2 -2 0
-2 -3 1
0 -1 0
-1 -2 0
1 -3
Output
-1
Input
5 1 3
1 0 0
2 -2 0
-2 -3 1
0 -1 1
-1 -2 0
1 0
Output
0
Note

"survive"

This statement has been modified to include the clarifications made during the competition.