#10486. 买零食

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

小蒜很喜欢在课间去小卖部买零食。然而不幸的是,这个学期他又有在一教的课,而一教的小卖部姐姐以冷若冰霜著称。

第一次去一教小卖部买零食的时候,小蒜由于不懂事买了好一大堆东西,被小卖部姐姐给了一个“冷若冰霜”的眼神,食欲都下降了很多。

从那以后,小蒜就学乖了,去小卖部买东西只敢同时买 3 包以内的零食,并且价格加起来必须是5的整数倍,方便小卖部姐姐算价格。

但是小蒜不擅长计算,所以他把小卖部里所有零食的价格以及他对这个零食的渴望度都告诉了你,希望你能够帮他计算出在不惹恼小卖部姐姐的前提下,能够买到零食的渴望度之和最高是多少?

输入格式

每个输入文件包含多组测试数据,在每个输入文件的第一行为一个整数 Q,表示测试数据的组数。

每组测试数据的第一行为一个正整数 N,表示小卖部中零食的数量。

接下来的 N 行,每行为一个正实数 A 和一个正整数 B,表示这种零食的价格和小蒜对其的渴望度。

一种零食仅有一包。

1 \le Q \le 10 1 \le N \le 50 0<A \le 10 1 \le B \le 100

A 的小数部分仅可能为 0.5 或 0。

输出格式

对于每组测试数据,输出一个整数 Ans,表示小蒜可以获得最大的渴望度之和。

样例

样例输入

1
4
0.5 6
4.5 7
5.0 4
2.0 9

样例输出

17