시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 1 1 1 100.000%

문제

In this problem, we will use Chebyshev distance on a Cartesian plane. The Chebyshev distance between two points $(p_x,p_y)$ and $(q_x,q_y)$ on the plane is $\max{\big(|p_x-q_x|,|p_y-q_y|\big)}$.

Let us define a donut on the plane as the set of points in a certain distance range from a certain point, the donut's center. More formally, the donut with center $(x_c,y_c)$, inner radius $l$ and outer radius $r$ is the set of points $(x,y)$ such that $l \leq \max{\big(|x-x_c|,|y-y_c|\big)} \leq r$.

There are $n$ points selected on the Cartesian plane. Points are numbered from $1$ to $n$, and each point has a score associated with it.

We want to place a donut on the plane. The inner radius of the donut will be $l$, the outer radius will be $r$, and the center of the donut is not yet determined: you have to decide where to place it. However, both coordinates of the center must be integers. After you place the donut, its score will be the sum of the scores of points which belong to the donut.

You are given the coordinates of the selected points and the score associated with each point. Calculate the maximum possible score of the donut you can place.

입력

The first line contains three integers: $n$, the number of selected points on the plane, $l$, the inner radius of the donut, and $r$, the outer radius of the donut ($1 \leq n \leq 10^5$, $1 \leq l \leq r \leq 10^9$).

The following $n$ lines describes selected points, one per line. Each of these lines contains three integers $x$, $y$, and $s$: the coordinates of the point and the score associated with it ($-10^9 \leq x, y \leq 10^9$, $-10^4 \leq s \leq 10^4$). Note that some points may coincide.

출력

Print the maximum score of the donut.

예제 입력 1

4 1 1
0 1 1
0 -1 1
1 0 -100
-1 0 -100

예제 출력 1

2

예제 입력 2

4 1 2
0 1 1
0 -1 1
1 0 -100
-1 0 -100

예제 출력 2

1