问题描述

小蓝所在学校周边新开业了一家游乐园，小蓝作为班长，打算组织大家去游乐园玩。已知一共有 $N$ 个人参加这次活动，游乐园有 $M$ 个娱乐项目，每个项目都需要买门票后才可进去游玩。门票的价格并不是固定的，团购的人越多单价越便宜，当团购的人数大于某个阈值时，这些团购的人便可以免费进入项目进行游玩。这 $M$ 个娱乐项目是独立的，所以只有选择了同一个项目的人才可以参与这个项目的团购。第 $i$ 个项目的门票价格 $H_i(X)$ 与团购的人数 $X$ 的关系可以看作是一个函数：

$H_i(X)=max⁡(K_i×X+B_i,0)$

其中 $max$ 表示取二者之中的最大值。当 $H_i=0$ 时说明团购人数达到了此项目的免单阈值。

这 $N$ 个人可以根据自己的喜好选择 $M$ 个娱乐项目中的一种，或者有些人对这些娱乐项目都没有兴趣，也可以选择不去任何一个项目。每个人最多只会选择一个娱乐项目，如果多个人选择了同一个娱乐项目，那么他们都将享受对应的团购价格。小蓝想知道他至少需要准备多少钱，使得无论大家如何选择，他都有能力支付得起所有 $N$ 个人购买娱乐项目的门票钱。

输入格式

第一行两个整数 $N$、$M$，分别表示参加活动的人数和娱乐项目的个数。接下来 $M$ 行，每行两个整数，其中第 $i$ 行为 $K_i$、$B_i$，表示第 $i$ 个游乐地点的门票函数中的参数。

输出格式

一个整数，表示小蓝至少需要准备多少钱，使得大家无论如何选择项目，自己都支付得起。

样例

4 2
-4 10
-2 7

12

样例说明

样例中有 $4$ 个人，$2$ 个娱乐项目，我们用一个二元组 $(a,b)$ 表示 $a$ 个人选择了第一个娱乐项目，$b$ 个人选择了第二个娱乐项目，那么就有 $4-a-b$ 个人没有选择任何项目，方案 $(a,b)$ 对应的门票花费为 $max⁡(-4×a+10,0)×a+max⁡(-2×b+7,0)×b$，所有的可能如下所示：

其中当 $a=1,b=2$ 时花费最大，为 $12$。此时 $1$ 个人去第一个项目，所以第一个项目的单价为 $10-4=6$，在这个项目上的花费为 $6×1=6$；$2$ 个人去第二个项目，所以第二个项目得单价为 $7-2×2=3$，在这个项目上的花费为 $2×3=6$；还有 $1$ 个人没去任何项目，不用统计；总花费为 $12$，这是花费最大的一种方案，所以答案为 $12$。

评测用例规模与约定

对于 $30\%$ 的评测用例，$1≤N,M≤10$。

对于 $50\%$ 的评测用例，$1≤N,M≤1000$。

对于 $100\%$ 的评测用例，$1≤N,M,B_i≤10^5$，$-10^5≤K_i<0$。