The device consists of several blocks. For each block, the probability of its failure-free operation for a certain time (reliability) is known. If at least one of the device blocks fails, the entire device ceases to work, and therefore the probability of failure-free operation of the entire device P is found as the product of the reliability of its blocks: P device = p1 · p2 · ... · pN.

To increase the reliability of the device, it was decided to backup some units. Block reservation is the connection of one or several of the same blocks in parallel to it. In the event of an accident of the first block, the second one will perform its functions, etc., this replacement will not affect the reliability of all other blocks.

We assume that the probability of failure-free operation of a group of K identical blocks (including the original one) is found as follows: p '= 1 - (1 - p) K, where p is the probability of failure-free operation of one such block. The probability of failure-free operation of the device is then defined as P'device = p'1 · p'2 · ... · p'N.

The cost of each unit and the amount S allocated for the modernization of the entire device are known. It is required to find the maximum probability of device uptime, which we can obtain, provided that the total cost of the added blocks should not exceed S.

Input data

The first line of the input contains an integer N - the number of blocks in the device (1 ≤ N ≤ 30). The next N lines contain two numbers separated by a space - the probability of failure-free operation of the next block pi and its cost si (pi is a real number, 0 <pi ≤ 1, si is an integer, 1 ≤ si ≤ 1000). The last line contains an integer S - the amount allocated for the modernization of the device (0 ≤ S ≤ 1000).

Output

Print one number - the probability of the device’s uptime after modernization with an accuracy of at least four digits after the decimal point.

For example:

Input:

3

0.6 10

0.7 14

0.8 8

30

Output:

0.62899

Skills: Python, C++ Programming

( 0 reviews ) Vologda, Russian Federation

Project ID: #22409390

8 freelancers are bidding on average \$32 for this job

utkarshkatiyar19

Hi, I'm an expert in C++ and python programming. I'm sure that I can easily do this project for you. We can have a chat about it. Thanks.

\$30 USD in 1 day
(334 Reviews)
7.2
panditthecoder

Hi, The problem you are posting is not straightforward as a brute force solution will be very expensive computationally. However, i have figured out a way to solve this which will be much faster than the brute force a More

\$25 USD in 5 days
(5 Reviews)
3.2
Alexsfodik

Hello. How are you. I'm software engineer and algorithm expert. I have many experiences in c, c++, c#, java, python, node.js. I can complete your project successfully. Thanks.

\$100 USD in 1 day
(2 Reviews)
2.8
monkeyMatrix

C++, Python Expert!!! I'm a expert in C ++, C#, I 've taken part in the National ACM Contest in 2016(that was Algorithm contest with C++ ) and win a gold medal. I have 8 years of experiences with C, C#, Unity. I have More

\$30 USD in 1 day
(5 Reviews)
2.6
hemsingh1

C++ Programming, Python skilled professional with the required expertise. Can help to deliver the solution as needed on the expected lines. Please private message me to discuss the project further. Hope to build a long More

\$36 USD in 7 days
(1 Review)
2.0
khizerali1

Hi Sir, Python Core Development Course from Saylani Welfare Trust,2019 06 Months CADCAM Creo 2.0 Course from KTDMC in Collaboration with NAVTTC 14-May to 30-October 2018 Certificate of Computer Operator from Saylani W More

\$10 USD in 7 days
(0 Reviews)
0.0
sayeemmdabdullah

I believe I will be the best person for your work. I am an Algorithm Expert and had solved lots of programming problems in different online judges. So hope you will give me your work.

\$10 USD in 1 day
(0 Reviews)
0.0
eliakh0ury

hello, i am a university student in computer engineering and i would be happy to solve your problem.

\$15 USD in 5 days
(0 Reviews)
0.0