Classes de memes per al Roura P54395
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 ≤ ti ≤ t, i 0 ≤ ki ≤ 105.
Sortida
Per a cada cas, escriviu el màxim “meme knowledge” que pot obtenir en Roura.
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
- Author
- Víctor Martín
- Language
- Catalan
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++