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 \le c_i \le 10^6$ 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 \le 8$.

• Test-2:   Entradas con $n \le 60$.

• Test-3:   Entradas de todo tipo.