蓝桥杯2023年第十四届省赛真题-最大开支

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

以参与这个项目的团购。第 i 个项目的门票价格 Hi 与团购的人数 X 的关系可以看作是一个函数：

Hi(X) = max (Ki × X + Bi , 0)

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

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

第一行两个整数 N、M，分别表示参加活动的人数和娱乐项目的个数。

接下来 M 行，每行两个整数，其中第 i 行为 Ki、Bi，表示第 i 个游乐地点的门票函数中的参数。

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

其中当 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⁵，−10⁵ ≤ K_i < 0。