#2888. 奖品

奖品

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

TeaLand\red{TeaLand }正在举办第一届 TeaCuP\red{TeaCuP}!他们准备设置一个金牌(第一名),两个银牌(第 二、三名)和四个铜牌(第四到七名)。

赞助商们为获奖者准备了 N\red{N }件奖品,第 i\red{i }件奖品的价值为 Ai\red{A_i,}每个获奖者会获得一 个奖品,设第 i\red{i }名获得的奖品价值为 Pi,\red{P_i,}选手想要 Pi\red{P_i }满足以下条件:

1.P1\red{1. P_1 ≥} P2\red{P_2 ≥} P3\red{P_3 ≥} P4\red{P_4 ≥} P5\red{P_5 ≥} P6\red{P_6 ≥} P7.\red{P_7.}

2.P1<P2+P3<P4+P5+P6+P7.\red{2. P_1 < P_2 + P_3 < P_4 + P_5 + P_6 + P_7.}

给定奖品的价值 Ai\red{A_i,}你需要最大化 Pi\red{P_i }之和,如果不存在任意一种方案则输出 1\red{-1}

输入格式

第一行一个整数 N\red{N }表示奖品个数。

第二行 N\red{N }个整数 Ai\red{A_i }表示奖品的价值。

输出格式

如果不存在方案则输出 1\red{-1,}否则输出最大的 Pi\red{P_i }之和。

样例

输入样例1

7
1 2 3 4 5 6 7

输出样例1

-1

输入样例2

8
1 2 3 4 5 6 7 8

输出样例2

35

输入样例3

10
5 5 5 5 5 5 10 5 5 5

输出样例3

35

提示

对于 20%\red{20\% }的数据保证 N\red{N ≤} 10\red{10}

对于 50%\red{50\% }的数据保证 N\red{N ≤} 103\red{10^3}

对于所有测试点保证 7\red{7 ≤} N\red{N ≤} 5×105\red{5 \times 10^5} , 1\red{1 ≤} Ai\red{A_i ≤} 2×108\red{2 \times 10^8}

国庆集训2

未参加
状态
已结束
规则
OI
题目
4
开始于
2022-10-1 14:01
结束于
2022-10-1 16:01
持续时间
2 小时
主持人
参赛人数
14