Tesoros al noreste P29540


Statement
 

pdf   zip

html

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 
Public test cases

  • 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
    • Information
    Author
    Dmytro Soboliev
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++