#13 「 bride 」

统计

随着川普的支持率逐日下降,让川普下台的呼声越来越大,国会被迫进行了一次表决,每一位议员都有权利选择支持川普还是反对川普,若反对的议员严格超过一半,则川普只能卸任。议员共 $N$ 个,每个议员有两个属性:威望度 $W_i$ 和忠诚度 $H_i$。在表决的时候,每个议员支持川普的概率为 $\frac{H_i}{100}$。

Kano 是一位腰缠万贯的企业家,出于个人原因,他想让川普下台。他拿出了 $K$ 百万元,想要通过贿赂议员的方式来增加川普下台的可能性。每个议员每收下 $1$ 百万元,那么他的忠诚度便会减少 $10$,减少到 $0$ 的时候就不可再减少了。

即便这样,表决还是可能以支持的结果收场,那么 Kano 将派出刺客,暗杀所有投了支持票的议员。设所有投了支持票的议员的威望度总和为 $S$,则成功暗杀的概率为 $\frac{A}{A+S}$($A$ 为常数)。若暗杀失败,则 Kano 也将会被捕。

现在 Kano 想知道,在最优策略下,自己被捕的可能性是多少?

输入格式

第一行,三个正整数 $N,K,A$

接下来 $N$ 行,每行一个正整数 $W_i$ 和一个非负整数 $H_i$

输出格式

输出一个小数(四舍五入保留 $6$ 位小数输出),表示在最优策略下,自己被捕的可能性。

样例数据

input1

5 6 80
12 90
15 80
22 70
45 60
147 50

output1

0.328491

input2

1 2 15
15 30

output2

0.050000

数据规模与约定

$N,K\le 9,~W_i,A\le 10000,~H_i\le100$

时间限制:1s

空间限制:512MB

Author: NanoApe