Clases de memes para Roura

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 t_(i) segundos y aporta
k_(i) 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 t_(i) k_(i). Suponed
1 ≤ t ≤ 3600, 0 ≤ n ≤ 500, 1 ≤ t_(i) ≤ t, y 0 ≤ k_(i) ≤ 10⁵.

Salida

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

[image]

Información del problema

Autoría: Unknown
Traducción: Salvador Roura

Generación: 2026-01-25T11:16:34.391Z

© Jutge.org, 2006–2026.
https://jutge.org
