Pegs and Legs

Pegs and Legs는 거의 수직인 판 위로 원반이 미끄러져 내려오는 게임이다. 판 아래쪽에는 원반이 떨어질 자리가 있고, 이를 leg라 부른다. 원반이 leg에 들어가면 그 leg가 가진 점수를 얻는다.

원반은 판 위쪽에서 시작해 어떤 drop point peg 또는 drop point leg에 직접 떨어뜨린다. 원반이 peg에 부딪히면 세 가지 중 하나가 일어난다. (1) 확률 $\ell$로 왼쪽으로 떨어진다. (2) 확률 $r$로 오른쪽으로 떨어진다. (3) 확률 $1 - \ell - r$로 걸려서 멈춘다. 확률은 peg마다 다를 수 있다. 원반이 왼쪽이나 오른쪽으로 떨어지면 다른 peg 또는 leg에 떨어진다. 원반이 걸려서 멈추면 위쪽의 어떤 drop point에서 다시 떨어뜨려야 한다. 아래 그림은 3번째 예제 입력을 나타내며, 어두운 peg 두 개가 drop point이다.

중력 때문에 원반을 다시 떨어뜨리지 않는 한 같은 peg에 두 번 부딪히는 일은 없다. 원반이 leg에 들어가면 게임이 끝나고 그 leg의 값을 얻는다. 플레이어가 얻을 수 있는 기대 점수의 최댓값은 얼마인가?

첫 번째 줄에는 leg의 개수 $L$ ($1 \leq L \leq 100\,000$)과 peg의 개수 $P$ ($1 \leq P \leq 100\,000$)가 주어진다. leg는 $1$부터 $L$까지 번호가 매겨지고, peg는 $L+1$부터 $L+P$까지 번호가 매겨진다.

다음 $L$개의 줄에는 leg에 대한 정보가 순서대로 주어진다. 각 줄에는 이 leg의 값 $v$ ($1 \leq v \leq 1\,000\,000$)가 하나의 정수로 주어진다.

다음 $P$개의 줄에는 peg에 대한 정보가 순서대로 주어진다. 각 줄은 이 peg에 부딪힌 뒤 원반이 왼쪽으로 떨어질 확률 $\ell$ ($0 < \ell < 1$)과 오른쪽으로 떨어질 확률 $r$ ($0 < r < 1$, $\ell + r \leq 1$)이 실수로 주어지고, 이어서 왼쪽으로 떨어질 때 도달하는 peg/leg의 번호 $x$ ($1 \leq x \leq L+P$)와 오른쪽으로 떨어질 때 도달하는 peg/leg의 번호 $y$ ($1 \leq y \leq L+P$)가 정수로 주어진다. $x$와 $y$는 이 peg의 번호보다 작음이 보장된다.

모든 실수는 소수점 아래 세 자리까지 정확히 주어진다. 어떤 peg 또는 leg로 떨어지는 peg가 하나도 없다면, 그 peg 또는 leg는 drop point이다.

어떤 peg에서든 그 peg에 도달한 뒤 원반이 결국 걸려서 멈출 확률은 $0.9999$ 이하임이 보장된다.

플레이어가 얻을 수 있는 기대 점수의 최댓값을 출력한다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이하인 답은 정답으로 인정된다.