Сережё $n$ элементтэй $a_1, a_2, ... , a_n$ дарааллийг дараах нөхцлүүдийг хангаж байвал үзэсгэлэнтэй гэж боддог. Үүнд:

• $x, y$ ($x ≠ y$) хос тоо бүрийн хувьд $x$ нь ч $y$ нь ч $a$-д агуулагддаг
• $x, y$ хос бүрийн хувьд $a_j = x$, $a_{j+1} = y$, эсвэл $a_j = y$, $a_{j+1} = x_j$ нөхцлийн ядаж нэг нь хангагдах $j$ ($1 ≤ j < n$) олддог байх

Серёжа $n$ элеменнтэй үзэсгэлэнтэй олонлог үүсгэхийг хүссэн. Серёжагийн найз Димад нийт $m$ тасалбар байгаа. Тасалбар бүр $q_i, w_i$ тоог агуулдаг. $i$-р тасалбар $w_i$ үнэтэй бөгөөд танд $a$ дараалалдаа $q_i$ тоог хүссэн удаа ашиглах боломжыг олгоно. $q_i$ утгууд бүгд хоорондоо ялгаатай. Серёжад ганц ч тасалбар байхгүй тул Диматай дараах наймааг хийх гэж байна. Дима $n$ элементтэй үзэсгэлэнтэй олонлог үүсгээд, түүнд оролцсон $q_i$ болгонд Серёжагаас $w_i$ рубль авна. Одоо тэд тохиролцоонд хүрсэн бөгөөд Серёжа найздаа төлж чадах хамгийн их мөнгөн дүнг олохыг хүсч байгаа.

Серёжагийн төлөх боломжит хамгийн их мөнгөн дүнг олно уу.

Оролт

Эхний мөрөнд $n$, $m$ ($1 ≤ n ≤ 2·10^6$, $1 ≤ m ≤ 10^5$) өгөгдөнө. Дараагийн $m$ мөр бүрт $q_i, w_i$ ($1 ≤ q_i, w_i ≤ 10^5$) байна. Бүх $q_i$ нь хоорондоо ялгаатай болно.

Гаралт

Нэг мөрөнд Серёжагийн төлж чадах хамгийн их мөнгөн дүнг хэвлэнэ үү.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

In the first sample Sereja can pay $5$ rubles, for example, if Dima constructs the following array: $[1, 2, 1, 2, 2]$. There are another optimal arrays for this test.

In the third sample Sereja can pay $100$ rubles, if Dima constructs the following array: $[2]$.