Tesoros al noreste P29540
En un cuadrado de tamaño D por D hay enterrados N tesoros. Sean (xi, yi) las coordenadas (enteros entre 0 y D−1, ambos inclusive) de la posición donde está enterrado el tesoro i-ésimo, valorado en wi 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 w1=1, w2=2 y w3=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 xi, yi y wi, separados por espacios. Se te garantiza que 1≤ wi≤ 106.
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≤ 3, D≤ 100. 20 Puntos
- TestB: Resolver varias entradas con N≤ 1000, D≤ 100. 20 Puntos
- TestC: Resolver varias entradas con N≤ 8, D≤ 109. 20 Puntos
- TestD: Resolver varias entradas con N≤ 1000, D≤ 109. 20 Puntos
- TestE: Resolver varias entradas con N≤ 105, D≤ 109. 20 Puntos
Input
3 5 1 2 2 0 0 1 2 1 3
Output
4
Input
7 11 0 0 4 1 4 2 2 3 5 1 3 7 4 1 6 5 3 5 2 10 6
Output
22
Input
7 100000001 0 0 4 10000000 40000000 2 20000000 30000000 5 10000000 30000000 7 40000000 10000000 6 50000000 30000000 5 20000000 100000000 6
Output
22
- Author
- Dmytro Soboliev
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++