[AdditionalFile5634.zip](file://AdditionalFile5634.zip?type=additional_file)

#5634. 「PA 2015 Final」Biznes

标签: 传统 | 时间限制: 10000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2015 Final Dopasowanie

企业家 Bajtazar 是一家新成立的制造企业 Bajtex 的老板。他现在计划引导 Bajtex 的发展，以便在最短的时间内让公司变得利润丰厚，从而使他这位总裁获得「商业巨鳄」的称号。我们称一家公司是利润丰厚的，如果其年收入达到至少 $D$ 百万拜塔拉（bajtalar）。

遗憾的是，目前 Bajtazar 只拥有一间生产厂房和 $p$ 百万拜塔拉的资本。他可以将这些资金用于购买生产机器。此外，一旦 Bajtex 开始产生利润，赚到的钱也可以用来购买更多的机器。

市场上共有 $n$ 种型号的机器。第 $i$ 种型号的机器价格为 $c_{i}$ 百万拜塔拉，并能提供每年 $d_{i}$ 百万拜塔拉的额外收入。购买同型号机器的数量没有限制。

请帮助 Bajtazar 确定他成为商业巨鳄所需的最短时间。假设购买机器（包括运输和安装）所花费的时间可以忽略不计，并且会立即增加公司的收入。此外，我们假设公司是持续盈利的，即对于任何年收入水平为 $x$ 百万拜塔拉的机器组合，在任何实数时间 $t \geq 0$ 年内，这些机器将恰好赚取 $t \cdot x$ 百万拜塔拉。

输入格式

输入的第一行包含三个整数 $n, D$ 和 $p$ $(1 \leq n \leq 100, 1 \leq D \leq 100000, 1 \leq p \leq 10^{9})$，分别表示机器型号的数量、要求的年收入水平（单位：百万拜塔拉）以及 Bajtazar 的初始资本（单位：百万拜塔拉）。

接下来的 $n$ 行包含对可用机器类型的描述。其中第 $i$ 行包含两个整数 $c_{i}$ 和 $d_{i}$ $(1 \leq c_{i} \leq 10^{9}, 1 \leq d_{i} \leq D)$，分别表示第 $i$ 型号机器的价格以及它能带来的年收入。

保证 Bajtazar 的初始资本足以购买至少一台机器。

输出格式

输出应包含一个实数，表示 Bajtex 变得利润丰厚、Bajtazar 获得「商业巨鳄」称号所需的最短时间（单位：年）。如果与答案的相对误差或绝对误差不超过 $10^{-6}$，则结果将被视为正确。

样例 1

输入

3 14 6
2 2
5 6
6 7

输出

0.783333333

在第二个样例中，最优策略是在公司运营之初购买第二种型号的机器。随后，每当 Bajtazar 拥有足够的资金时，他就会购买第一种型号的机器，直到他成为商业巨鳄（也就是说，总共需要四台这样的机器）。从购买上一台机器起，他可以分别在 $\frac{1}{6}$、$\frac{2}{8}$、$\frac{2}{10}$ 和 $\frac{2}{12}$ 年后购买下一台第一种型号的机器。

样例 2

输入

1 1 1
1 1

输出

0.000000000

在第二个样例中，Bajtazar 拥有足够的资本，在公司运营之初就能成为商业巨鳄。