Операції

Дано $n$ цілих чисел $a_1,a_2,\dots ,a_n$. Спочатку вони всі рівні нулю.

Дано $m$ операцій, кожен з яких описується двома числа $k_i$ та $c_i$, які означають, що ви можете $k_i$ разів вибрати будь-який елемент з масиву $a$ та замінити його значення на $c_i$. Зверніть увагу, що елементи, які ви вибираєте, не обов'язково мають бути різними. Також ви не зобов'язані робити $i$-ту операцію рівно $k_i$ разів, ви можете виконати її будь-яку кількість разів, але не більше $k_i$. Також ви можете не виконувати операцію взагалі.

Всі $m$ операцій ви маєте виконувати послідовно. Тобто, спочатку всі заміни першої операції, потім другої, і так далі.

Знайдіть максимальну можливу суму масиву, що може вийти в кінці.

Giriş verilənləri

Перший рядок містить два цілі числа $n$ та $m$ ($1\le n,m\le 10^5$).

Кожен з наступних $m$ рядків містить по два цілі числа $k_i$ та $c_i$ ($1\le k_i,c_i\le 10^5$).

Çıxış verilənləri

Виведіть одне ціле число.

Nümunələr