Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
C. Серёжа ба тоон байрлуулалт
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Сережё $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 стриймийг ашиглана уу.
Орчуулсан: zoloogg
Жишээ тэстүүд
Оролт
5 2 1 2 2 3
Гаралт
5
Оролт
100 3 1 2 2 1 3 1
Гаралт
4
Оролт
1 2 1 1 2 100
Гаралт
100
Тэмдэглэл
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]$.