QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[+3]
Statistics

小德是北京大学的一名学生助教。现在一学期的课程结束了,老师希望小德能统计学生的最终成绩,并提交给教务。根据小德的观察,一位老师累加分数的过程可以被下述过程描述:

  1. 假设这一门课程有 n 个项目,每个项目的得分都是一个保留到小数点后一位的实数。小德记项目得分的可重集合为 S
  2. 重复若干次操作,每一次操作老师会从下面 A,B 两个方案中选择一个执行,直到 S 只剩下一个项目得分:
    • A. 老师在 S 中取出一个项目的得分 x,将 x 四舍五入到整数后作为新的项目得分放回 S
    • B. 老师在 S 中取出两个不同的项目的得分 x,y,将 x+y 作为新的项目得分放回 S
  3. 老师取出 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

子任务

对于所有数据:1T104,1n106, 0ai<10

子任务编号 数据范围 特殊性质 分值
1 n5 20
2 T100,n12 15
3 n80 17
4 ai 都是 0.2 的倍数 21
5 27