#P0823. Are you sure?
Are you sure?
题目描述
你们正在参加一项越野跑团体比赛。你们队有 名队员,其中第 名队员的速度是 , 体重是。
比赛允许每位队员单独行动或背负另一位队员行动。
当队员 背着队员 时:
- 如果队员 的体重大于或等于队员 的体重,则队员 的速度保持不变,为 。
- 如果队员 的体重小于队员 的体重,则队员 的速度将减少,减幅为两者体重之差,变为 。
- 如果,那么成员 就无法搬运成员 。
每名成员最多只能携带一名其他成员。如果一名成员被携带,他不能同时携带另一名成员。
对于所有未被携带的成员,速度最慢的成员的速度就是整个团队的速度。
求全队可能的最大速度。
输入格式
本题含有多组测试数据。
第一行输入一个正整数,表示测试用例数量。
接下来对于每组测试数据,第一行输入一个整数,表示团队成员人数。
接下来 行,每行输入两个整数 和 ,表示第 名队员的速度和重量。
题目保证:在单个测试文件中。
输出格式
对于每组测试用例,输出一行一个整数,表示整个团队可能的最大速度。
样例
2
5
10 5
1 102
10 100
7 4
9 50
2
1 100
10 1
8
1
提示
样例的第一个测试用例的最佳策略如下:
让成员 携带成员 。由于 ,成员 的速度保持不变,仍然是 。
让成员 携带成员 。由于 ,成员 的速度将减少 ,变为 。
成员 将单独行动,他的速度为 。
因此答案是 。