La venjança de Cthulhu P13061


Statement
 

pdf   zip

thehtml

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 ei i la mala sort mi 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 ei mi. Podeu suposar 1 ≤ s ≤ 104, 1 ≤ n ≤ 100, 1 ≤ ei ≤ s, i 1 ≤ mi ≤ 109.

Sortida

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





Public test cases

  • Input

    100 5
60 40
75 60
90 80
20 25
20 25

1000 4
998 5
997 10
2 100
3 120

10 5
2 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000

    Output

    90
220
5000000000
    • Information
    Author
    Enrique Jiménez
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++