This is not a submission-based problem.

This is not an interactive problem.

Xiao Xiu and Xiao Dong are building a spanning forest together.

They each have a graph with $n$ vertices and $m$ edges. They want to select a subset of edges such that the graph containing only these edges is a forest or a unicyclic forest.

Since Xiao Xiu and Xiao Dong are a couple, they decide to make the same choices. Specifically, for the $i$-th edge, both of them must either select it or not select it.

Each $i$-th edge has a weight $a_i$. Xiao Xiu and Xiao Dong want to maximize the total weight of the selected edges.

Here, a unicyclic forest is defined as a graph where each connected component is either a tree or a unicyclic graph (a graph with exactly one cycle).

Input

The first line contains two integers $n$ and $m$, representing the number of vertices and edges in the graphs.

The next line contains two integers $\text{type}_1$ and $\text{type}_2$, representing the requirements for the final graph for Xiao Xiu and Xiao Dong, respectively. If $\text{type}$ is $1$, the requirement is a forest; if $\text{type}$ is $2$, the requirement is a unicyclic forest.

The next $m$ lines each contain five integers $u1_i, v1_i, u2_i, v2_i, a_i$, where $u1_i, v1_i$ are the vertices connected by the edge in Xiao Xiu's graph, and $u2_i, v2_i$ are the vertices connected by the edge in Xiao Dong's graph.

The input does not guarantee the absence of multiple edges or self-loops.

Output

Output a single integer representing the maximum total edge weight.

Examples

Input 1

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

Output 1

4

Subtasks

For all data, $1 \le n, m \le 300$ and $1 \le a_i \le 10^5$.

Unless otherwise specified, the following limits apply.