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 pirmajā rindā ir doti divi skaitļi N un M (1 ≤ N ≤ 10⁴, 1 ≤ M ≤ 10³), 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 ≤ 10³), 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.

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

Testu apakšgrupas:

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