Hay \(n\) trabajos; el trabajo \(i\) ocupa el intervalo de tiempo \([s_i, e_i)\) y paga \(p_i\). Elige trabajos que no se superpongan para ganar lo más posible. Un trabajo puede empezar justo en el instante en que termina otro.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 5 \cdot 10^4)\) y siguen \(n\) líneas con \(s_i\), \(e_i\) y \(p_i\) \((1 \le s_i < e_i \le 10^9,\ 1 \le p_i \le 10^4)\).

Salida

La máxima ganancia.

Ejemplo 1

Entrada

4
1 3 50
2 4 10
3 5 40
3 6 70

Salida

120

Ejemplo 2

Entrada

5
1 3 20
2 5 20
3 10 100
4 6 70
6 9 60

Salida

150

Ejemplo 3

Entrada

3
1 2 5
1 3 6
1 4 4

Salida

6

Basado en el problema 1235 de LeetCode, Maximum Profit in Job Scheduling, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.