Дано n цілих чисел a1,a2,…,an. Спочатку вони всі рівні нулю.
Дано m операцій, кожен з яких описується двома числа ki та ci, які означають, що ви можете ki разів вибрати будь-який елемент з масиву a та замінити його значення на ci. Зверніть увагу, що елементи, які ви вибираєте, не обов'язково мають бути різними. Також ви не зобов'язані робити i-ту операцію рівно ki разів, ви можете виконати її будь-яку кількість разів, але не більше ki. Також ви можете не виконувати операцію взагалі.
Всі m операцій ви маєте виконувати послідовно. Тобто, спочатку всі заміни першої операції, потім другої, і так далі.
Знайдіть максимальну можливу суму масиву, що може вийти в кінці.
Перший рядок містить два цілі числа n та m (1≤n,m≤105).
Кожен з наступних m рядків містить по два цілі числа ki та ci (1≤ki,ci≤105).
Виведіть одне ціле число.