← 返回题目列表

Codeforces · 1431/A

A. 卖汉堡包

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

自助餐厅里有 $$$n$$$ 名顾客。他们每个人都想买一个汉堡包。第 $$$i$$$ 个顾客拥有 $$$a_i$$$ 硬币,如果汉堡的花费最多为 $$$a_i$$$ 硬币,他们就会购买一个汉堡。

假设汉堡的成本为 $$$m$$$。那么自助餐厅赚取的硬币数量就是 $$$m$$$ 乘以购买汉堡的人数(如果汉堡的价格为 $$$m$$$)。你的任务是计算自助餐厅可以赚取的最大金币数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 客户数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个客户拥有的硬币数量。

输出

对于每个测试用例,打印一个整数 - 自助餐厅可以赚取的最大硬币数量。

示例

输入 #1

6
3
1 1 1
3
4 1 1
3
2 4 2
8
1 2 3 4 5 6 7 8
1
1000000000000
3
1000000000000 999999999999 1

输出 #1

3
4
6
20
1000000000000
1999999999998

注意

示例测试用例说明:

1.汉堡的最佳价格为$$$m = 1$$$,因此购买$$$3$$$个汉堡,食堂赚取$$$3$$$币;
2.汉堡的最佳价格为$$$m = 4$$$,因此购买$$$1$$$汉堡,食堂赚取$$$4$$$金币;
3.汉堡的最佳价格为$$$m = 2$$$,因此购买$$$3$$$个汉堡,食堂赚取$$$6$$$金币;
4.汉堡的最佳价格为$$$m = 4$$$,因此购买$$$5$$$个汉堡,食堂赚取$$$20$$$金币;
5.汉堡的最佳价格为$$$m = 10^{12}$$$,因此购买$$$1$$$汉堡,食堂赚取$$$10^{12}$$$币;
6. 汉堡的最佳价格是 $$$m = 10^{12} - 1$$$,因此购买了 $$$2$$$ 个汉堡,自助餐厅赚取 $$$2 \cdot 10^{12} - 2$$$ 硬币。