小德是北京大学的一名学生助教。现在一学期的课程结束了,老师希望小德能统计学生的最终成绩,并提交给教务。根据小德的观察,一位老师累加分数的过程可以被下述过程描述:
- 假设这一门课程有 n 个项目,每个项目的得分都是一个保留到小数点后一位的实数。小德记项目得分的可重集合为 S。
- 重复若干次操作,每一次操作老师会从下面 A,B 两个方案中选择一个执行,直到 S 只剩下一个项目得分:
- A. 老师在 S 中取出一个项目的得分 x,将 x 四舍五入到整数后作为新的项目得分放回 S。
- B. 老师在 S 中取出两个不同的项目的得分 x,y,将 x+y 作为新的项目得分放回 S。
- 老师取出 S 中唯一的项目得分 x,将 x 四舍五入到整数后提交给教务。
小德是一名善良的学生,作为过来人,他希望给学生尽可能高的成绩。小德想知道,按照上述加分规则,他提交给教务的成绩最高可能是多少,你能帮帮他吗?
输入格式
本题的测试点包含有多组测试数据。
第一行一个正整数 T 表示测试数据组数。
下面每组测试数据第一行一个正整数 n,表示课程的项目数。
接下来一行 n 个实数 ai,每个数小数点后都恰有一个数字。
输出格式
对于每组数据,一行一个整数表示答案。
样例数据
输入格式
2
2
4.4 5.4
6
0.4 0.3 7.3 2.3 4.3 3.3
输出格式
10
19
子任务
对于所有数据:1≤T≤104,1≤∑n≤106, 0≤ai<10。
子任务编号 | 数据范围 | 特殊性质 | 分值 |
---|---|---|---|
1 | n≤5 | 无 | 20 |
2 | T≤100,n≤12 | 无 | 15 |
3 | n≤80 | 无 | 17 |
4 | 无 | ai 都是 0.2 的倍数 | 21 |
5 | 无 | 无 | 27 |