Vaca Pogo


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

En un intento mal concebido para aumentar la movilidad de su vaca ganadora Bessie, el Granjero Juan le ha puesto un palo de pogo a cada una de las patas de Bessie. Bessie ahora puede saltar rápidamente a través de la granja, pero todavía no ha aprendido a desacelerar.

Para que Bessie logre mejor control, el Granjero Juan arma un curso de práctica para ella a través de un camino uni-dimensional a lo largo de su granja. En varias posiciones distintas en el camino, el pone N objetivos en los cuales Bessie debe aterrizar. Bessie comienza en la ubicación de cualquier objetivo de su elección y se le permite moverse únicamente en una dirección, saltando de objetivo en objetivo. Cada salto debe cubrir al menos tanta distancia como el salto previo y debe aterrizar en un objetivo.

Bessie recibe puntaje por cada objetivo que ella toque (incluyendo el objetivo en el cual comienza). Por favor, calcule el máximo número de puntos que ella puede obtener.

Entrada:

  • Línea 1: El entero N (1 \leq N \leq 10^3).

  • Líneas 2, \dots, 1+N: La línea i+1 contiene x_i y p_i, cada uno un entero en el rango 0, \dots, 10^6.

Salida:

  • Línea 1: El máximo número de puntos que Bessie puede recibir.

Entrada de ejemplo:

6
5 6
1 1
10 5
7 6
4 8
8 10

Hay 6 objetivos. El primero está en la posición x=5 y vale 6 puntos, y así sucesivamente.

Salida de ejemplo:

25

Bessie salta desde la posición x=4 (8 puntos) a la posición x=5 (6 puntos), luego a la posición x=7 (6 puntos) y finalmente a la posición x=10 (5 puntos).


Comments

There are no comments at the moment.