# La venjança de Cthulhu

Com potser sabreu, l'any passat els participants del SWERC van fer un
gran descobriment: mitjançant un ritual es pot invocar el gran Cthulhu,
sacrificar un integrant de l'equip, i a canvi rebre un AC. Però els
equips de la UPC van provocar la ira de Cthulhu gosant fer massa
invocacions, i al SWERC d'enguany Cthulhu es va venjar. El seu pla va
ser sinistre: La nit abans del SWERC, va fer sorgir un cementiri al
costat de l'hotel on estaven els equips de la UPC, i la mala sort que
duen els cementiris va condemnar els equips UPC al fracàs.

Cthulhu va haver de resoldre el següent problema: Donada la superfície
$s$ del cementiri, el nombre de tombes disponibles $n$, i l'espai $e_i$
i la mala sort $m_i$ de cada tomba $i$, cal maximitzar la suma de mala
sort sense que la suma d'espais excedeixi $s$. El gran Cthulu sap
resoldre aquest problema (ell ho sap tot), però com a servents seus li
heu de fer la feina bruta.

## Entrada

L'entrada consisteix en diversos casos, només amb naturals, cadascun amb
$s$ i $n$, seguits de $n$ parells $e_i$ $m_i$. Podeu suposar
$1 \le s \le 10^4$, $1 \le n \le 100$, $1 \le e_i \le s$, i
$1 \le m_i \le 10^9$.

## Sortida

Per a cada cas, escriviu la màxima mala sort que no sobrepassi la
superfície disponible.

::: center
![image](foto.eps){width="0.9 \\textwidth"}
:::

## Informació del problema

Autoria: Enrique Jiménez

Generació: 2026-01-25T10:06:27.782Z

© *Jutge.org*, 2006--2026.\
<https://jutge.org>
