Classes de memes per al Roura P54395


Statement
 

pdf   zip

thehtml

Un fet extremadament greu va posar en perill la primera edició de l’Olimpíada Informàtica Catalana: L’enunciat del problema xungo feia necessària l’intervenció d’un personatge i, en lloc de fer l’obvi en aquests casos, que és usar un dels memes del moment, en Roura va decidir posar una referència desafortunada a Chiquito de la Calzada. En fi...

L’únic mètode per evitar la repetició d’una barbàrie similar passa per sometre en Roura a unes classes de memes. Però, com que ell no és conscient de la gravetat de la situació, només està disposat a rebre una sola classe mestra amb una durada màxima de t segons.

Disposeu d’n vídeos, on l’i-èsim dura ti segons i aporta ki unitats de “meme knowledge”. A més, per apurar al màxim els t segons totals, podeu ensenyar al Roura alguns segons de balls de Fortnite, cadascun dels quals aporta una unitat de “meme knowledge”. Assumint que no cal gens de temps per canviar de vídeo, o per canviar de vídeo a Fortnite o al revés, podeu maximitzar el“meme knowledge” que obtindrà en Roura?

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters. Cada cas comença amb t i n, seguides d’n parells ti ki. Suposeu 1 ≤ t ≤ 3600, 0 ≤ n ≤ 500, 1 ≤ tit, i 0 ≤ ki ≤ 105.

Sortida

Per a cada cas, escriviu el màxim “meme knowledge” que pot obtenir en Roura.






 ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍ ‍
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
    Catalan
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++