Problem C - Flamel Goes to Spain

Q: When the Philosophers speak of gold and silver, from which they extract their matter, are we to suppose that they refer to the vulgar gold and silver?
A: By no means; vulgar silver and gold are dead, while those of the Philosophers are full of life.

(Alchemical Catechism, Paracelsus, Sec. XVI)

Nicolas Flamel was a famous alchemist born in Paris in 1330. Flamel made it his life's work to understand the text of a mysterious twenty-one-page book he had purchased and that has been identified by a sage as the Book of Abraham also known as the Codex. Around 1378 he traveled to Spain for assistance with translation, but before hitting the road he had a problem to solve.

No alchemist would travel without their vast collection of flasks and vials, all of them full of mysterious substances of extreme importance for their work. Flamel was no exception. He wanted to carry as much substances as possible but he didn't have enough containers to bring all of them. Traveling with this kind of substances required some specially designed containers.

But Flamel had a plan. He made a list of all the substances he could not live without. This list included the quantity needed of each substance and also the quantity he had stored. Then he found out the price of each substance in Spain. His idea was to take with him larger quantities of each substance he needed and then sell the excess and buy those he didn't bring. This was an incredible smart plan as some of his containers were much larger than he needed but he could not mix two different potions in the same container.

The Problem

Given a list of substances and containers, discover the best way to accommodate the substances in the containers in order to make a profit when selling the substances in excess. This profit should be enough to buy substances not carried by Flamel. As the price of substances in Spain was much higher than in France he decided to make the maximum profit possible.

For instance, if Flamel had 3 litters of ammonia, 2.5 litters of alcohol and 0.5 litters of formic acid, and he needed to carry at least 0.5 litters of each of these substances in one single container with a 5 litter capacity, he wouldn't be able to do so because he coulnd't mix substances.

But if he knew he could sell ammonia in Spain for 23 maravedis/l (the maravedis was one of Spanish many currencies at the time) and buy alcohol for 10 maravedis/l and formic acid for 15 maravedis/l, he could bring 3 litters of ammonia, sell 2.5 litters for 57.5 maravedis and use 5 maravedis to buy 0.5 litters of alcohol and 7.5 maravedis to buy 0.5 litters of formic acid. He would even make a profit of 45 maravedis.

Input

The first line of the input contains a single integer p representing the number of different potions possessed by Flamel . This line will be followed by p lines each one of them describing a substance. Each of these lines will contain two real numbers qt (the quantity Flamel has of the substance) and mn (the minimum quantity of the substance Flamel must have when in Spain) and one integer sp (the price of the substance in Spain in maravedis).

The following will always be true: 1 <= p, qt, mn <= 100 ; mn <= qt and 1 <= sp <= 1000.

The next line will contain two integers: n (1 <= n <= 100) representing the number of containers Flamel possesses and c (1 <= c <= 50) the capacity of each container in litters.

Output

The output should contain a single line, with a real number, precise to the 3rd decimal place, representing the profit Flamel can make with his plan, or the world impossible if it isn't possible to get the minimum quantities of each substance he desires.

Example Input 1

3
3 0.5 23
2.5 0.5 10
0.5 0.5 15
1 5

Example Output 1

45.000

Example Input 2

3
3 0.5 23
2.5 0.5 10
0.5 0.5 15
1 1

Example Output 2

impossible

CPUP 2007
Universidade do Porto
(10/10/2007)