La venjança de Cthulhu P13061

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.