Clases de memes para Roura P54395


Statement
 

pdf   zip

thehtml

Un hecho terrible puso en peligro la primera edición de la Olimpiada Informática Catalana: El enunciado del problema chungo necesitaba la intervención de un personaje, y en lugar de hacer lo obvio en estos casos, que es usar uno de los memes del momento, Roura decidió poner una referencia desafortunada a Chiquito de la Calzada. En fin...

El único método para evitar la repetición de una barbarie similar pasa por someter a Roura a unas clases de memes. Pero, como él no es consciente de la gravedad de la situación, sólo está dispuesto a recibir una sola clase maestra con una duración máxima de t segundos.

Disponéis de n videos, donde el i-ésimo dura ti segundos y aporta ki unitades de “meme knowledge”. Además, para apurar los t segundos totales, podéis enseñar a Roura algunos segundos de bailes de Fortnite, y cada uno aporta una unidad más de “meme knowledge”. Asumiendo que no se requiere ningún tiempo para cambiar de video, ni para cambiar de video a Fortnite o al revés, podéis maximizar el“meme knowledge” que Roura obtendrá?

Entrada

La entrada consiste en varios casos, sólo con números enteros. Cada caso empieza con t y ‍n, seguidas de n pares ti ki. Suponed 1 ≤ t ≤ 3600, 0 ≤ n ≤ 500, 1 ≤ tit, y 0 ≤ ki ≤ 105.

Salida

Para cada caso, escribid el máximo “meme knowledge” que Roura puede obtener.






 ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍
Public test cases
  • Input

    301 6
    125 500
    75 150
    300 1000
    300 400
    125 400
    100 600
    
    3600 1
    2000 1999
    
    1000 4
    100 200
    200 200
    400 200
    800 200
    

    Output

    1251
    3600
    1100
    
  • Information
    Author
    Víctor Martín
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++