### 问题描述 小蓝所在学校周边新开业了一家游乐园，小蓝作为班长，打算组织大家去游乐园玩。已知一共有 $N$ 个人参加这次活动，游乐园有 $M$ 个娱乐项目，每个项目都需要买门票后才可进去游玩。门票的价格并不是固定的，团购的人越多单价越便宜，当团购的人数大于某个阈值时，这些团购的人便可以免费进入项目进行游玩。这 $M$ 个娱乐项目是独立的，所以只有选择了同一个项目的人才可以参与这个项目的团购。第 $i$ 个项目的门票价格 $H_i(X)$ 与团购的人数 $X$ 的关系可以看作是一个函数： $$H_i(X) = \max(K_i \times X + B_i,0)$$ 其中 $\max$ 表示取二者之中的最大值。当 $H_i = 0$ 时说明团购人数达到了此项目的免单阈值。 这 $N$ 个人可以根据自己的喜好选择 $M$ 个娱乐项目中的一种，或者有些人对这些娱乐项目都没有兴趣，也可以选择不去任何一个项目。每个人最多只会选择一个娱乐项目，如果多个人选择了同一个娱乐项目，那么他们都将享受对应的团购价格。小蓝想知道他至少需要准备多少钱，使得无论大家如何选择，他都有能力支付得起所有 $N$ 个人购买娱乐项目的门票钱。 ### 输入格式 第一行两个整数 $N$、$M$，分别表示参加活动的人数和娱乐项目的个数。接下来 $M$ 行，每行两个整数，其中第 $i$ 行为 $K_i$、$B_i$，表示第 $i$ 个游乐地点的门票函数中的参数。 ### 输出格式 一个整数，表示小蓝至少需要准备多少钱，使得大家无论如何选择项目，自己都支付得起。 ### 样例输入 ```text 4 2 -4 10 -2 7 ``` ### 样例输出 ```text 12 ``` ### 样例说明 样例中有 $4$ 个人，$2$ 个娱乐项目，我们用一个二元组 $(a,b)$ 表示 $a$ 个人选择了第一个娱乐项目，$b$ 个人选择了第二个娱乐项目，那么就有 $4-a-b$ 个人没有选择任何项目，方案 $(a,b)$ 对应的门票花费为 $\max(-4 \times a + 10,0) \times a + \max(-2 \times b + 7,0) \times b$，所有的可能如下所示： | a | b | 花费 | | :--: | :--: | :--: | | 0 | 0 | 0 | | 0 | 1 | 5 | | 0 | 2 | 6 | | 0 | 3 | 3 | | 0 | 4 | 0 | | 1 | 0 | 6 | | 1 | 1 | 11 | | 1 | 2 | 12 | | 1 | 3 | 9 | | 2 | 0 | 4 | | 2 | 1 | 9 | | 2 | 2 | 10 | | 3 | 0 | 0 | | 3 | 1 | 5 | | 4 | 0 | 0 | 其中当 $a=1,b=2$ 时花费最大，为 $12$。此时 $1$ 个人去第一个项目，所以第一个项目的单价为 $10-4=6$，在这个项目上的花费为 $6 \times 1=6$；$2$ 个人去第二个项目，所以第二个项目得单价为 $7-2 \times 2=3$，在这个项目上的花费为 $2 \times 3=6$；还有 $1$ 个人没去任何项目，不用统计；总花费为 $12$，这是花费最大的一种方案，所以答案为 $12$。 ### 评测用例规模与约定 对于 $30$% 的评测用例，$1 \le N, M \le 10$。 对于 $50$% 的评测用例，$1 \le N, M \le 1000$。 对于 $100$% 的评测用例，$1 \le N, M, B_i \le 10^5$，$-10^5 \le K_i < 0$。