#2481. 「CEOI2017」Sure Bet

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

题目描述

现在有 n 个A类灯泡和 n 个B类灯泡,每个灯泡都有各自的权值。
我们将这些灯泡分为 n 组,每组包含一个来自A类的灯泡和一个来自B类的灯泡。
你可以从中选取任意个灯泡,每选取一个灯泡需要花费 1 的代价。
在你选取完之后,系统会随机在A类和B类中选择一个类型,并点亮那一类的所有灯泡。你选取的每个点亮的灯泡会给你带来等于它权值的收益。
现在请你合理选取灯泡,以最大化可能的最小收益。你只需要求出来这个收益即可。

输入格式

第一行一个正整数 n ,表示灯泡的组数。
接下来 n 行每行两个空格隔开的实数 A_i,B_i 。分别表示属于这组的A灯泡和B灯泡的权值。输入的实数不会超过四位小数。

输出格式

输出最大化的最小可能收益,请输出到小数点后恰好四位。

样例

样例输入

4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5

样例输出

0.5000

样例解释

最优策略是选择第一组的B灯泡和第三组的A灯泡和第四组的A灯泡:

  • 如果B类灯泡被点亮,收益是 3.7-3=0.7
  • 如果A类灯泡被点亮,收益是 1.6+1.9-3=0.5

最小可能收益是 0.5

数据范围与提示

对于所有测试点,有 1.0\le A_i,B_i\le 1000.0

  • 子任务 1( 20\% ):有 1\le n\le 10
  • 子任务 2( 40\% ):有 1\le n\le 1000
  • 子任务 3( 40\% ):有 1\le n\le 100\ 000