Є рюкзак місткістю ~V~ мм~^3~. Є ~N~ сипучих речовин:

• першої з них є у наявності ~v_1~ мм~^3~, причому вона має питому вартість ~p_1~ коп/мм~^3~;
• другої є ~v_2~ мм~^3~, з питомою вартістю ~p_2~ коп/мм~^3~;
• ... і так далі ...,
• до ~N~-ої, якої є ~v_N~ мм~^3~, з питомою вартістю ~p_N~ коп/мм~^3~.

Кожної з цих речовин можна взяти будь-яку кількість в межах наявної, й вартість узятої (частини) речовини дорівнюватиме добутку взятої кількості на питому вартість. Інакше кажучи, ~i~-ої речовини можна взяти будь-яку кількість ~a_i~ в межах ~0\leqslant a_i\leqslant v_i~, й вартість узятої (частини) буде ~a_i\cdot p_i~. Якщо взяти кілька різних речовин (повністю чи частково), сумарна вартість усього взятого визначатиметься як сума щойно згаданих добутків для всіх узятих (повністю чи частково) речовин.

Яку найбільшу сумарну вартість цих речовин можна набрати, не перевищивши місткість рюкзака? Припускаємо, ніби сипучі речовини можна розділити одну від одної, зовсім не втративши на цьому корисний об'єм рюкзака.

Вхідні дані

Перший рядок містить об'єм рюкзака ~V~ (~10\leqslant V\leqslant 10^9~). Другий рядок містить кількість речовин ~N~ (~1\leqslant N\leqslant 10^5~). Кожен з подальших ~N~ рядків містить спочатку кількість відповідної сипучої речовини ~v_i~ (~1\leqslant v_i\leqslant 10^7~), потім (через пробіл) її питому вартість ~p_i~ (~1\leqslant p_i\leqslant 10^7~). ~V~ та ~v_i~ вимірюються у мм~^3~, ~p_i~ – у коп/мм~^3~, ~N~ у штуках (безрозмірна).

Результати

Ваша програма повинна вивести єдине число – максимальну можливу вартість (у копійках) вибраних (частин) речовин.

Приклади

Вхід

200
3
10 40000
50 2000
2000 5

Результат

500700