B. Хулгайч ба чүдэнзнүүд

хугацааны хязгаарлалт 0.5 секунд

санах ойн хязгаарлалт 64 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хулгайч чүдэнзний агуулахад нэвтэрсэн бѳгѳѳд аль болох ихийг хулгайлахыг хүсэв. Агуулахад $m$ контэйнэр байсан, $i$-р контэйнэр $a_i$ чүдэнзний хайрцагтай, чүдэнзний хайрцаг бүр дотроо $b_i$ чүдэнзтэй байв. Бүх чүдэнзний хайрцаг ижил хэмжээтэй. Хулгайчийн цүнх яг $n$ хайрцаг хийх багтаамжтай. Таны даалгавар хулгайчийн авч явж чадах хамгийн чүдэнзний тоог олох юм. Түүнд чүдэнзнүүдийг ѳѳр ѳѳр хайрцагт шилжүүлэн хийх хугацаа байгаагүй тул тэрээр ердѳѳ чүдэнзний тоо хамгийн их байхаар $n$-ээс олонгүй чүдэнзний хайрцгийг сонгох боломжтой юм.

Оролт

Эхний мѳр $n$ ($1 ≤ n ≤ 2·10^8$) болон $m$ ($1 ≤ m ≤ 20$) бүхэл тоонуудыг агуулна. $i + 1$-р мѳр $a_i$, $b_i$ ($1 ≤ a_i ≤ 10^8$, $1 ≤ b_i ≤ 10$) хосыг агуулна. Оролтын бүх тоонууд бүхэл тоо байна.

Гаралт

Бодлогын хариу болох ганц бүхэл тоог гарга.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
7 3
5 10
2 5
3 6
Гаралт
62
Оролт
3 3
1 3
2 2
3 1
Гаралт
7
Сэтгэгдлүүдийг ачааллаж байна...