#P2016. 表演艺术(artist)

表演艺术(artist)

【问题描述】

凡和邻家男孩玩完了纸牌,兴致很高,于是准备了一场表演艺术对抗赛。他特意请来了很多表演艺术家,分成绿黑两队,进行名为PK,实则捞金的表演。

凡为了捞金,开设了一个赌局,在比赛开始之前招揽人们来押注谁能胜出,在所有人进行投注之后,凡需要告诉大家绿方和黑方的单位返还金额都是多少。

举个例子,如果绿方的单位返还金额为5,那么我每押1块钱绿方胜,如果成真就能拿回5块钱,但是如果结果绿方输了,我就拿不回来任何钱

凡决定将单位返还金额设得更具有吸引力,所以他要求“绿方胜的单位返还金额+黑方胜的单位返还金额=T”,并且为了赚更多的钱,凡可以在中间某两个投注的人之间更改单位返还金额,但是要求双方的总和仍然为T,并且只能更改一次

不幸的是,凡突然发现自己请来的表演艺术家竟然和众多投注人是一伙的,也就是说,在凡定下单位返还金额之后,那些艺术家会操纵比赛结果,从而让凡拿出更多的钱来

这下凡有些慌了,于是他来询问你应该怎么制定单位返还金额

【输入格式】

第一行一个整数N,代表投注的人的个数

接下来N行,每行两个实数ai,bi代表第i个人投注黑方胜和绿方胜的资金

最后一行一个实数T,含义如题目中所示

【输出格式】

一个实数,代表你最少返还的金额(保留两位小数)

【样例输入1】

3
0 10
10 0
10 0
10

【样例输出1】

0.00

【样例解释1】

一种最优方案是:

第一次投注及之前,单位返还金额为10和0

第二次投注及之后,单位返还金额为0和10

这样无论哪方胜利,你都不会返还任何金钱

【样例输入2】

2
5 5
5 5
1

【样例输出2】

5.00

【样例解释2】

一种最优方案是:

第一次投注及之前,单位返还金额为0.5和0.5

第二次投注及之后,单位返还金额为0.5和0.5

这样无论哪方胜利,你的返还金额都为5

【数据范围与约定】

测试点编号 N
1 = 2
2 ≤ 10
3
4 ≤ 1000
5
6 ≤ 100000
7
8 ≤ 500000
9
10

对于所有数据,0<=ai,bi,T<=100,且至多精确到两位小数