Buffet libre P28082

Considerad un restaurante de buffet libre con una sola hilera de n platos. Cada plato i aporta c_i calorías. Además, tiene asignado un número x_i, de manera que si se coge ese plato, no se puede coger ninguno de los siguientes x_i platos ni a su derecha ni a su izquierda. Conociendo los valores c_i y x_i de cada plato, ¿podéis calcular el número máximo de calorías que se pueden ingerir?

Entrada

La entrada consiste en varios casos. Cada caso empieza con una n entre 1 y 1000. Siguen n pares de naturales c_i x_i, con 1 ≤ c_i ≤ 10⁶ y x_i < n.

Salida

Para cada caso, escribid el número máximo de calorías que se pueden ingerir.

Puntuación

• Test-1:   Entradas con n ≤ 8.  17 Puntos 

• Test-2:   Entradas con n ≤ 60.  25 Puntos 

• Test-3:   Entradas de todo tipo.  58 Puntos