# 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 \le t \le 3600$, $0 \le n \le 500$, $1 \le t_i \le t$, y
$0 \le k_i \le 10^5$.

## Salida

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

::: center
![image](cesc.eps){width="7.5cm"}
:::

## 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>
