神牛今天很开心，家里购置的新房就要领钥匙了，新房里有一间他的专属房间。而早上妈妈告诉他房间需要哪些物品自己说了算，只要不超过N元就行。

于是神牛很开心的做预算，因为他想要的物品有m件那么多，总价会超过N元，所以他把每件物品的价格v_i和在心目中的重要度t_i标在物品后面。

并且他认为自己的满足度k是：将所选的每件物品的价格与重要度的乘积相加得到的和。前提是花费不能超出N元。

作为神牛的好朋友神犇，你非常理解神牛的想法：

假设将选定的物品从0编号，那么神牛的满足度为：

k = v_0 × t_0 + v_1 × t_1 + .....

现在你需要帮神牛计算k的最大值。

第一行，有单个空格分隔的两个整数N,m，分别表示妈妈给神牛的最大额度和清单中的物品数量。

接下来m行，每行两个整数v_i,t_i，分别表示第i个物品的价格和重要度。

对于100%的数据：

1\le N \le 30000 ；

1\le m \le 25 ；

1\le v_i \le 10000 ；

1\le t_i \le 5 。

一行，一个正整数，