Tesoros al noreste P29540

En un cuadrado de tamaño $D$ por $D$ hay enterrados $N$ tesoros. Sean $(x_i, y_i)$ las coordenadas (enteros entre $0$ y $D-1$, ambos inclusive) de la posición donde está enterrado el tesoro $i$-ésimo, valorado en $w_i$ euros.

Sólo se te permite entrar en el cuadrado por la casilla $(0,0)$, y puedes recoger tantos tesoros como te sea posible con una única condición: únicamente puedes avanzar hacia el este (incrementar la coordenada $x$ en 1) o hacia el norte (incrementar la coordenada $y$ en 1).

Por ejemplo: si $D=5$ y hubiera $N=3$ tesoros situados en $(0,0)$, $(1,2)$ y $(2,1)$ y valorados en $w_1=1$, $w_2=2$ y $w_3=3$ respectivamente, podrías ir del $(0,0)$ al $(1,2)$ y acumular un total de 3 euros, o ir del $(0,0)$ al $(2,1)$ y acumular un total de 4 euros, pero no te sería posible visitar los tres tesoros (lo intentes como lo intentes, en algún momento tendrías que avanzar hacia el sur o hacia el oeste).

Entrada

Cada entrada contiene un único caso de pruebas. Su primera línea contiene los números $N>0$ y $D>0$. A continuación vienen $N$ líneas con los valores $x_i$, $y_i$ y $w_i$, separados por espacios. Se te garantiza que $1\le w_i\le 10^6$.

Salida

Escribe una línea (acabada en salto de línea) con el valor máximo de los tesoros que es posible recoger.

Puntuación

• TestA:   Resolver varias entradas con $N\le 3, D\le 100$.

• TestB:   Resolver varias entradas con $N\le 1000, D\le 100$.

• TestC:   Resolver varias entradas con $N\le 8, D\le 10^9$.

• TestD:   Resolver varias entradas con $N\le 1000, D\le 10^9$.

• TestE:   Resolver varias entradas con $N\le 10^5, D\le 10^9$.