$Alien$们比较非主流脑残，在秋收季节他们喜欢玩“穿越田野$CrossField$”即$CF$。假设田野是一个无穷大的矩阵，里面的一些格点$(X_i,Y_i)$有栋栋种植的能量植物，每个植物有$W_i$的能量。一开始$Alien$位于$1$号植物，$Alien$每次可以使用$K$能量从$i$号植物跳到$Y_j=Y_i$且$X_j > X_i$或$X_j=X_i$且$Y_j > Y_i$的$j$号植物，然后获得植物的能量。

现在$Alien$要你帮忙设计一个方案，使得可以从$1$号植物到达$N$号植物，并且剩余能量最大。

输入格式

第一行两个整数$N，K$。

接下来$N$行，每行三个数，表示$i$号植物的$X_i,Y_i,W_i$。

输出格式

输出共一行一个数$Ret$，表示最大的剩余能量。

样例

样例输入

8 10
1 1 15
2 2 30
1 2 8
2 1 7
3 2 8
2 3 7
4 2 100
3 3 15

样例输出

36

【样例解释】

$(1,1)->(1,2)->(2,2)->(3,2)->(3,3)$；

数据范围与提示

• 对于$30$%数据：$1 \leq N \leq 500；1 \leq K \leq 20；0 \leq Xi,Yi \leq 500；0 \leq Wi \leq 20$；
• 对于$60$%数据：$1 \leq N \leq 5,000$；
• 对于$100$%数据：$1 \leq N \leq 100,000；1 \leq K \leq 1,000；0 \leq Xi,Yi \leq 10^5；0 \leq Wi \leq 1,000$；
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$65536\mathrm{KB}$

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载