Pegs and Legs

문제

Pegs and Legs is a game where a disk slides down a nearly-vertical board. At the bottom of the board are places for the disk to land, called legs. Each leg is worth a certain amount of points if your disk lands in it.

You start with a disk at the top and drop it onto some drop point peg or directly into some drop point leg. When your disk hits a peg, one of three things happen: (1) the disk falls to the left with probability $\mathrm{\ell }\backslash ell$, (2) the disk falls to the right with probability $rr$, or (3) it gets stuck with probability $1-\mathrm{\ell }-r1\; -\; \backslash ell\; -\; r$. The probabilities may be different for each peg. If the disk falls to the left or to the right, then it will either fall onto another peg or into a leg. If the disk gets stuck, then you must drop it again from some drop point on the top. The figure below illustrates the 3rd sample input, the two dark pegs are the drop points.

Because of gravity it is not possible for a disk to hit the same peg more than once unless the disk is dropped again. The game continues until your disk lands in a leg, at which point you earn the value of that leg. What is the maximum possible expected score the player can earn?

입력

The first line of input contains two integers $LL$ ($1\le L\le 1000001\; \backslash leq\; L\; \backslash leq\; 100\backslash ,000$), which is the number of legs, and $PP$ ($1\le P\le 1000001\; \backslash leq\; P\; \backslash leq\; 100\backslash ,000$), which is the number of pegs. Legs are numbered from $11$ to $LL$ and pegs are labeled from $L+1L+1$ to $L+PL+P$.

The next $LL$ lines describe the legs, in order. Each of these lines contains a single integer $vv$ ($1\le v\le 10000001\; \backslash leq\; v\; \backslash leq\; 1\backslash ,000\backslash ,000$), which is the value of this leg.

The next $PP$ lines describe the pegs, in order. Each of these lines starts with two real numbers $\mathrm{\ell }\backslash ell$ (), which is the probability that the disk falls to the left after hitting this peg, and $rr$ (), which is the probability that the disk falls to the right after hitting this peg ($\mathrm{\ell }+r\le 1\backslash ell\; +\; r\; \backslash leq\; 1$), followed by two integers $xx$ ($1\le x\le L+P1\; \backslash leq\; x\; \backslash leq\; L+P$), which is the label of the peg/leg the disk falls onto if it falls to the left, and $yy$ ($1\le y\le L+P1\; \backslash leq\; y\; \backslash leq\; L+P$), which is the label of the peg/leg the disk falls onto if it falls to the right. It is guaranteed that $xx$ and $yy$ are smaller labels than the label of this peg.

All real numbers are specified to exactly 3 decimal places. A peg or leg is a drop point if there are no pegs that drop into this peg or leg.

It is guaranteed that from any peg (whether a drop point or not), the probability the disk eventually gets stuck after reaching this peg is at most $0.99990.9999$.

출력

Display the maximum possible expected score the player can earn. Answers with an absolute error or relative error of at most ${10}^{-6}10^\{-6\}$ will be accepted.

2 4
344969
539194
0.508 0.318 1 1
0.990 0.009 1 3
0.807 0.041 3 1
0.225 0.617 4 4

539194.0000000000

2 8
684841
506003
0.277 0.692 1 1
0.007 0.864 2 1
0.783 0.067 2 1
0.962 0.026 3 1
0.580 0.171 4 4
0.997 0.003 1 6
0.548 0.207 8 7
0.537 0.238 5 7

684556.2033270609

3 3
11
12
10
0.500 0.500 1 2
0.800 0.100 1 4
0.600 0.400 4 3

11.0555555556