Problem Statement

watasou and hibit are playing baseball.
watasou throws the balls (pitcher), and hibit hits them (batter).

watasou has $N$ balls, and ball $i \ (1 \leq i \leq N)$ is thrown at speed $K_i$ to coordinates $(X_i, Y_i)$.

• You can solve this problem without caring where the $2$-dimensional plane is located,
  but as a mental image, consider the $2$-dimensional plane containing "the pitcher-side face of the strike zone, which is a pentagonal prism".

watasou is going to choose $1$ or more balls from the $N$ balls and throw them to hibit in any order.

• More strictly, for an integer sequence $S = (S_1, S_2, \dots, S_M)$ obtained by taking $M \ (1 \leq M \leq N)$ elements from the permutation $(1, 2, \dots, N)$ and arranging them in any order, he throws ball $S_j$ as the $j \ (1 \leq j \leq M)$-th pitch.

watasou has seen through hibit's tendencies and knows that hibit cannot hit the ball thrown as the $j \ (1 \leq j \leq M)$-th pitch if and only if it satisfies at least $1$ of the following conditions.

• $j = 1$
• $j = 2$ and $A \leq dist(S_{j}, S_{j-1})$
• $2 \leq j \leq M$ and $B \leq |K_{S_j} - K_{S_{j-1}}|$
• $3 \leq j \leq M$ and $A \leq dist(S_{j}, S_{j-1}) + dist(S_{j}, S_{j-2})$

Here, $dist(S_i, S_j) = |X_{S_i} - X_{S_j}| + |Y_{S_i} - Y_{S_j}|$ (Manhattan distance).

watasou wants to throw as many balls as possible while keeping the number of times hibit hits a ball at $0$.
Find the maximum number of balls watasou can throw under this requirement.

Input

$N\ A\ B$
$X_1\ Y_1\ K_1$
$X_2\ Y_2\ K_2$
$\vdots$
$X_N\ Y_N\ K_N$

• $2 \leq N \leq 14$
• $-1000 \leq X_i,Y_i \leq 1000 \ (1 \leq i \leq N)$
• $1 \leq A \leq 4000$
• $1 \leq B \leq 10^6$
• $1 \leq K_i \leq 10^6 \ (1 \leq i \leq N)$
• All inputs are integers.

Output

Output the answer on $1$ line.

Sample

3 3 4
2 1 4
2 2 3
4 4 7

3

2 1 1
0 0 1
0 0 1

1

4 40 50
10 30 140
40 55 150
50 60 165
55 60 160

4