Description

In biology class, little F learned about food chains and food webs.

He learned that energy decreases step by step. For example, on a food chain, between two linked organisms $A \rightarrow B$ (meaning $B$ eats $A$), the energy transfer efficiency is at most $\frac 1 5$; and by studying interspecific relationships, one can guide energy to flow toward the parts most beneficial to humans.

Now, little F wants to study energy flow, so he creates an ecological system in his mind.

In this ecological system, there are $n+2$ species, where $0$ is the producer and the total energy flowing through the entire ecosystem is fixed by it; you are the greedy apex predator $n + 1$, and you can prey on all species; the other predators $[1, n]$ each have their own preferences and will only prey on species with indices in $[0, r_i]$. Due to a naturally formed hierarchy of strength, these relationships satisfy $r_i \leq r_{i + 1}(1 \leq i < n),$ $r_i < i(1 \leq i \leq n)$.

Each animal needs to ingest at least $a_i$ units of energy to survive; the energy ingested by one organism can be passed to its predators, but the transfer efficiency never exceeds $\frac 1 5$. That is, suppose that organism $i$ captures $b_i$ units of energy, and the total energy $c_i$ obtained by all predators that prey on it satisfies:

• $b_i \geq a_i$;
• $c_i \leq \frac 1 5 b_i$.

You want to know, under the constraint that all organisms survive, what is the maximum energy you can obtain in the optimal arrangement.

Input Format

The first line contains two integers $n, a_0(1 \leq n \leq 10 ^ 5, 1 \leq a_0 \leq 10 ^ 9)$, where $a_0$ is the fixed energy of the producer.

Then follow $n$ lines, each with $2$ positive integers, representing $a_i, r_i(1 \leq a_i \leq 10 ^ 9)$.

It is guaranteed that $0\leq r_i < i, r_i \leq r_{i + 1}$.

Output Format

Output one floating-point number on a single line, representing the maximum energy you—the apex predator—can obtain. If it is impossible to make all organisms survive (including yourself), output $-1$.

Your answer will be considered correct if the relative or absolute error does not exceed $10 ^ {-8}$. If your program is correct, you do not need to worry about precision issues.

2 9
1 0
1 1

0.2000000

2 9
1 0
1 0

-1

2 10
1 0
1 0

0.4000000

Hint

Sample 1 explanation:

In the optimal arrangement:

• Predator 1 preys on producer 0, captures 5 units of energy, with transfer efficiency $\frac 1 5$, and obtains 1 unit of energy.
• Predator 2 preys on producer 0, captures 4 units of energy, with transfer efficiency $\frac 1 5$, and obtains 0.8 units of energy.
• Predator 2 preys on predator 1, captures 1 unit of energy, with transfer efficiency $\frac 1 5$, and obtains 0.2 units of energy.

Unfortunately, you can only prey on predator 2, capture 1 unit of energy, and obtain 0.2 units of energy.

Sample 2 and 3 explanation:

Since predator 2 goes on a diet and stops eating meat (or perhaps cannot defeat 1), the required energy from the producer changes from 9 units to 10 units.

Subtasks:

• Subtask $1(21 \mathrm{pts}) : n \leq 100$;
• Subtask $2(89 \mathrm{pts}) : n \leq 10 ^ 5$.

Translated by ChatGPT 5