The goal of this problem is to find the sum of the weights of all bridges in an infinite undirected graph. This undirected graph has the following properties:

(1) The graph is connected. (2) All nodes in the graph are divided into layers: layer 1, layer 2, layer 3, and so on. There are infinitely many layers, and each layer contains $n$ nodes. For convenience, we denote the $x$-th node of the $i$-th layer as $(i, x)$. (3) Nodes within the same layer can be connected to each other, and nodes in adjacent layers can be connected to each other. Apart from these, no other nodes can be connected. (4) If there is an edge with weight $d$ between $(i, x)$ and $(i, y)$, then there is also an edge between $(j, x)$ and $(j, y)$ with weight $0.9^{j-i}d$, where $j$ is any positive integer. (5) If there is an edge with weight $d$ between $(i, x)$ and $(i+1, y)$, then there is also an edge between $(j, x)$ and $(j+1, y)$ with weight $0.9^{j-i}d$, where $j$ is any positive integer.

The undirected graph shown below satisfies all the above properties.

An infinite undirected graph is connected if and only if there exists a path connecting any two nodes in the graph. An edge is a bridge if and only if the graph becomes disconnected after removing this edge.

Please write a program to read this infinite connected graph and calculate the sum of the weights of all its bridges. For example, in the figure above, the edge shown with a thick line is the only bridge in the graph, so the sum of the weights of the bridges in the figure is $1$.

Input

The first line contains three non-negative integers $n$, $m_1$, and $m_2$ separated by spaces. From the 2nd line to the $(m_1 + 1)$-th line, each line contains three positive integers $x$, $y$, and $d$, representing an edge with weight $d$ between $(1, x)$ and $(1, y)$. From the $(m_1 + 2)$-th line to the $(m_1 + m_2 + 1)$-th line, each line contains three positive integers $x$, $y$, and $d$, representing an edge with weight $d$ between $(1, x)$ and $(2, y)$.

The three integers in each line are separated by a space. There may be more than one edge between two nodes $x$ and $y$ in the graph, and the two nodes connected by an edge may be the same.

Output

Output a single line containing a real number, which is the sum of the weights of all bridges, rounded to two decimal places.

Examples

Input 1

3 1 3
1 2 4
1 2 5
2 3 3
3 3 1

Output 1

1.00

Note 1

This is the example given in the problem description.

Input 2

1 1 1
1 1 100
1 1 1

Output 2

10.00

Constraints

In 100% of the data, $d \le 100$.