개구리 왕눈이
시간 제한1초메모리 제한128 MB
리프 1에서 N까지 오른쪽 또는 위쪽 축 방향 이동만 허용되고 이동마다 K의 힘이 소모될 때, 파리를 먹어 얻는 힘을 최대로 남기는 경로를 찾는 문제입니다.
문제
개구리 왕눈이는 연꽃잎이 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번 연꽃잎에 도착한 뒤 가질 수 있는 힘의 최댓값을 한 줄에 출력한다.