题目描述

小婷需要采购恰好不少于 $n$ 份原料。共有 $m$ 位供应者，第 $i$ 位的单价为 $p_i$，最多供应 $a_i$ 份。每份原料可以单独购买，且所有供应量之和不少于需求量。求满足需求的最小费用。

输入格式

第一行两个整数 $n,m$。接下来 $m$ 行每行两个整数 $p_i,a_i$。

输出格式

输出最小费用。

输入

348615 2
853 741227
202 1176176

输出

70420230

输入

156743 3
473 1617094
722 471379
7 1750727

输出

1097201

输入

1687987 3
983 757036
829 1177249
199 1024674

输出

753796603

数据范围

$0\le n,a_i\le2\times10^6$，$0\le m\le5000$，$0\le p_i\le1000$。