URI Online Judge | 2580

Master Pokémon Ho

By Lucas Maciel, UFMG BR Brasil

Timelimit: 1

In Belo Horizonte, an electronic game has taken the streets and squares of the city: it is the pokémon Ho. The NlogNintendo startup that created the game did not expect such success. And she just hired you to find out the best way to become a master Pokémon Ho.

In Pokemon Ho, you have pokeballs that catch pokémons (game creatures). Each time a new Pokémon is captured, experience is gained, however repeated pokémons do not. A pokémon master Ho is a player with a lot of experience. And that's why you want to capture as many different types of Pokémon as possible. However, this is not an easy task. The Pokémon, when trying to be captured, can break the Pokeballs. Some more easily than others. In fact, for each pokémon i we have an associated probability pi of the pokémon to break the pokeball. To prevent some Pokémon from being captured, NlogNintendo assumed that pi ≤0.9. That is, at least 10% chance of catching a Pokémon is guaranteed. Furthermore, after each j-th attempt fails, pokemon i has a probability r {i, j} to escape the battle. If the Pokémon escapes, you can not try to capture it again. Since there are many attempts, NLogNintendo only offers Ri chance of escaping for each pokémon i. The probabilities ri, j, 1 ≤j ≤Ri are repeated at each Ri step.

NlogNintendo sent you the following task: Given the probabilities and capture experiences associated with each Pokemon and a finite number of Pokeballs, find the expected experience value to be obtained by assuming that the Pokemon Master Ho always plays optimally.

Input

The input consists of two N integers (1 ≤N ≤ 30) and P (1 ≤P ≤106) representing the number of pokémons in the game, and the number of pokeballs available to the player. The next 2*N rows have a string Si (1 ≤ |Si|≤50) (∀1 ≤iN), an integer Ri (1 ≤Ri ≤104) (∀1 ≤iN), an integer ei (1 ≤ei ≤1000) (∀1 ≤i N) and a real of 3 decimal places pi (0.000 ≤pi ≤0.900) (∀1 ≤iN) representing the name of the pokemon i, the number of probabilities to escape from a Battle, the experience gained by capturing it and the probability of the pokémon i break the pokeball, respectively. In the next line Ri real numbers r {i, j} (0.000 ≤r{i, j} ≤1,000) (∀1 ≤iN) (∀1 ≤jRi) representing the probability of the i-th pokemon escaping Of the battle after the j-th capture attempt. Remember that with every Ri attempts, the values repeat themselves.

Note: It is not guaranteed that if two pokémons appear with the same name in the entry, they will have all values associated.

Output

A real number rounded to 4 decimal places corresponding to the expected experience to be gained by a pokémon master Ho.

Input Samples Output Samples

2 1
Pikachu 3 100 0.500
0.500 0.100 0.900
Charmander 1 80 0.100
0.000

72.0000

2 2
Pikachu 3 100 0.500
0.500 0.100 0.900
Charmander 1 80 0.100
0.000

124.2000

5 1000000
Pikachu 3 100 0.500
0.500 0.100 0.900
Raichu 3 300 0.899
0.900 0.200 0.700
Charmander 1 80 0.100
0.000
Bulbasaur 1 80 0.125
0.000
Squirtle 1 80 0.050
0.000

344.1143