← 返回题目列表

Codeforces · 1379/C

C. 选择鲜花

中文机器翻译题面 查看原题

弗拉基米尔想给他的妻子准备一份礼物:他们有周年纪念日!他决定给她买$$$n$$$的花。

Vladimir去了一家花店,他惊讶地发现那里出售的鲜花有$$$m$$$种,而且每种花都无限量供应。弗拉基米尔想选择鲜花来最大限度地提高妻子的幸福感。他知道,在收到第 $$$i$$$ 类型的第一朵花后,妻子的幸福感增加了 $$$a_i$$$,并且在连续收到这种类型的每一朵花后,她的幸福感增加了 $$$b_i$$$。也就是说,如果在所选的花中存在 $$$x_i > 0$$$ 类型为 $$$i$$$ 的花,则他的妻子将获得 $$$a_i + (x_i - 1) \cdot b_i$$$ 额外的幸福(如果没有 $$$i$$$ 类型的花,则她不会获得该特定类型的任何东西)。

请帮助弗拉基米尔正确选择 $$$n$$$ 鲜花,以最大限度地提高他妻子的幸福感。

输入

第一行包含唯一的整数$$$t$$$ ($$$1 \leq t \leq 10\,000$$$),测试用例的数量。接下来是测试用例的 $$$t$$$ 描述。

每个测试用例描述都以两个整数 $$$n$$$ 和 $$$m$$$ 开头($$$1 \le n \le 10^9$$$, $$$1 \le m \le 100\,000$$$),Vladimir 需要选择的花朵数量以及可用花朵的类型数量。

以下 $$$m$$$ 行描述了花的类型:每行包含整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$),表示第 $$$i$$$ 种可用的花类型。

测试用例由空行分隔。保证所有测试用例的值$$$m$$$之和不超过$$$100\,000$$$。

输出

对于每个测试用例,输出一个整数:在最佳选择 $$$n$$$ 花后,Vladimir 的妻子的最大总幸福感。

示例

输入 #1

2
4 3
5 0
1 4
2 2

5 3
5 2
4 2
3 1

输出 #1

14
16

注意

在第一个示例中,Vladimir 可以摘 1 朵第一类型的花和 3 朵第二类型的花,在这种情况下,总幸福感等于 $$$5 + (1 + 2 \cdot 4) = 14$$$。

在第二个例子中,Vladimir 可以摘 2 朵第一类花、2 朵第二类花和 1 朵第三类花,在这种情况下,总幸福感等于 $$$(5 + 1 \cdot 2) + (4 + 1 \cdot 2) + 3 = 16$$$。