Nosaukums
Volframa diegs (wolfram_yarn)
Laika limits
0.50s
Atmiņas limits
32.0 MB
Grūtība
53%

Definīcija

Pasaules ekonomika zeļ un plaukst. Volframa diega tirgus ir kļuvis ļoti liels. Ir daudzi pircēji un daudzi tirgotāji. Ir tā sagadījies, ka viens no šiem tirgotājiem ir Gudrinieku ciems. Gudrinieku ciems gadā saražo N metrus ar volframa diegu. Ir pieejamas M cenas dažāda garuma volframa diegiem līdz garumam N. Gudrinieku ciems, protams, vēlas pārdot saražoto diegu pēc iespējas izdevīgāk. Uzdevums ir noteikt, kādos garumos ir jāsadala N garumā dotais diegs, lai to pārdodot, tiktu iegūta vislielākā peļņa. Ievērojiet, ka nav obligāti pārdot visu diegu, kaut kas var arī palikt pāri.


Ievaddatu raksturojums

Ievaddatu pirmajā rindā ir doti divi skaitļi N un M (1 ≤ N ≤ 104, 1 ≤ M ≤ 103), diega garums un dažādu garumu cenu skaits.

Katrā nākamajā no M rindām ir doti divi naturāli skaitļi a un b (1 ≤ a ≤ N, 1 ≤ b ≤ 103), diega garums, kuru tirgotājs vēlās iegādāties un cena, par kādu tirgotājs ir gatavs iegādāties diegu garumā a.


Izvaddatu raksturojums

Izvaddatos ir jāizvada viens skaitlis, maksimālā summa, kuru Gudrinieku ciems var iegūt, sadalot savu diegu visoptimālākajā iespējamajā veidā.


Piezīmes

Testu apakšgrupas:

  • 1 ≤ N ≤ 104 un 1 ≤ M ≤ 10 dod 30%.
  • Pārējie testi dod 70%

Paraugdati

Stdin
10 2
1 1
3 10
Stdout
31

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.