← 返回题目列表

Codeforces · 335/F

F. 买一送一

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

附近的一家馅饼店正在进行特价促销。对于您支付全价购买的每个馅饼,您可以选择一个价值严格较低的馅饼免费获得。考虑到您想要购买的所有馅饼的价格,确定您必须为所有馅饼支付的最低总金额。

输入

输入将以整数 n (1 ≤ n ≤ 500000) 开头,即您希望获得的馅饼数量。接下来是一行包含 n 个整数,每个整数表示一个馅饼的成本。所有成本均为不超过 109 的正整数。

输出

打印获得所有馅饼的最低成本。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

6
3 4 5 3 4 5

输出 #1

14

输入 #2

5
5 5 5 5 5

输出 #2

25

输入 #3

4
309999 6000 2080 2080

输出 #3

314159

注意

在第一个测试用例中,您可以支付成本 5 的馅饼并免费获得成本 4 的馅饼,然后支付成本 5 的馅饼并免费获得成本 3 的馅饼,然后支付成本 4 的馅饼并免费获得成本 3 的馅饼。

在第二个测试用例中,您必须为每个馅饼支付全价。