C. Gambler's Chocolate Cove
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the city of Wonkville, inside the world-famous chocolate factory is a lottery system called the Upside-Down Chocolate Room. Here, delightful treats are hidden behind a series of magical upside-down slot machines. Contestants who may enter the room follow a curious tradition: instead of pulling levers downward, they prefer to pull them upwards!

As a contestant in the Chocolate Room, you are given a set of $$$k$$$ slot machines, each with an associated reward distribution. Each slot machine $$$i$$$ generates rewards according to a known finite, discrete probability distribution $$$P_i$$$. You have a total of $$$n$$$ pulls to distribute among the $$$k$$$ slot machines. Your task is to maximize your expected winnings after these $$$n$$$ pulls. After $$$n$$$ pulls, what is the value of your expected winnings?

Input

The first line contains two integers $$$n$$$ and $$$k$$$ for $$$1 \leq n,k \leq 100$$$.

The following $$$3k$$$ lines contain three separate lines for each slot machine $$$1 \leq i \leq k$$$:

  • the number of elements $$$1 \leq m_i \leq 1000$$$ in $$$R_i$$$ and $$$P_i$$$, for all $$$1\leq i\leq k$$$
  • the reward distribution $$$R_i$$$ as $$$m_i$$$ space-separated distinct integers $$$r_1\: r_2\: ... \: r_{m_i}$$$ for $$$0\leq r_i\leq 100$$$ followed by
  • the probability distribution $$$P_i$$$ as $$$m_i$$$ space-separated real values $$$p_1 \: p_2\: ... \: p_{m_i}$$$ for $$$0 \leq p_i \leq 1$$$ with up to 8 digits after the decimal point. It is guaranteed that $$$p_1+ p_2+ ... + p_{m_i}=1$$$.
Output

Please determine the maximum expected winnings from $$$k$$$ slot machines after $$$n$$$ pulls.

Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{−6}$$$.

Example
Input
5 3
5
1 3 9 7 3
0.15 0.4 0.1 0.2 0.15
2
8 7
0.5 0.5
3
1 2 3
0.25 0.30 0.45
Output
37.5