개구리 왕눈이

개구리 왕눈이는 연꽃잎이 N개 있는 연못에 산다. 연꽃잎에는 1번부터 N번까지 번호가 매겨져 있다. 연못을 위에서 보면 각 연꽃잎의 위치를 2차원 평면 위의 점으로 나타낼 수 있다. 왕눈이는 좌표축에 평행한 방향으로만, 그리고 양의 방향으로만 뛸 수 있다. 즉 (x1, y1)에서 (x2, y2)로 뛰려면 다음 두 조건 중 하나를 만족해야 한다.

• x2 > x1 이고 y2 = y1
• y2 > y1 이고 x2 = x1

한 번 뛰는 데에는 힘이 K만큼 든다. 힘이 K보다 작으면 더 이상 뛸 수 없다. 왕눈이는 처음에 1번 연꽃잎에 있으며 N번 연꽃잎으로 가려 하고, 처음 힘은 0이다.

각 연꽃잎에는 파리가 산다. 왕눈이는 자신이 있는 연꽃잎의 파리를 먹을 수 있고, 파리 한 마리를 먹을 때마다 힘을 1 회복한다. 처음 힘이 0이므로, 첫 도약을 하려면 먼저 1번 연꽃잎의 파리를 먹어 힘을 얻어야 한다는 점에 주의하자.

왕눈이가 규칙에 따라 이동해 N번 연꽃잎에 도착했을 때, 도착한 뒤 가질 수 있는 힘의 최댓값을 구하여라.

첫째 줄에 연꽃잎의 수 N과 한 번 뛰는 데 필요한 힘 K가 주어진다. (2 ≤ N ≤ 300000, 1 ≤ K ≤ 1000)

이어지는 N개의 줄에는 각 연꽃잎의 좌표 X, Y와 파리의 수 F가 순서대로 주어진다. i+1번째 줄의 정보는 i번 연꽃잎에 대한 것이다. 서로 다른 연꽃잎의 좌표는 모두 다르다. (0 ≤ X, Y ≤ 100000, 0 ≤ F ≤ 1000)

입력은 항상 N번 연꽃잎에 도달하는 방법이 존재하도록 주어진다.

N번 연꽃잎에 도착한 뒤 가질 수 있는 힘의 최댓값을 한 줄에 출력한다.