The 2D plane is divided into several simple polygons. Each simple polygon shares at least one edge with another polygon, and the intersection of the areas of any two polygons is zero. The union of all polygons forms a single simple polygon (i.e., the case shown in Figure 1 does not occur).

A region is defined as: a polygon, or the complement of the union of all polygons with respect to the plane.

As shown in Figure 2, the black frames represent the boundaries of three simple polygons, and there are 4 regions in total on the plane.

Each edge $\langle p, q \rangle$ of a simple polygon has two directions ($p \to q$ and $q \to p$), and each direction has an activation cost $V$. If $V=0$, that direction of the edge cannot be activated. As shown in Figure 3, once a direction is activated, one can move infinitely many times from the counter-clockwise side of the vector $\langle p, q \rangle$ to the clockwise side, but not from the clockwise side to the counter-clockwise side. That is, one can move from region $A$ to region $B$, but not from region $B$ to region $A$.

Wayne wants you to find a region $a$ such that for any region $b$, it is possible to reach $b$ starting from $a$. Find the minimum total activation cost for such a region $a$. It is guaranteed that such a region exists.

Input

The first line contains two integers $n$ and $m$, representing the number of points and line segments, respectively.

The next $n$ lines each contain two integers $x$ and $y$, representing the coordinates of the $i$-th point, with points numbered from $1$ to $n$.

The next $m$ lines each contain four integers $p$, $q$, $V_1$, and $V_2$, representing a line segment connecting point $p$ to point $q$, where the cost to activate the $p \to q$ direction is $V_1$, and the cost for the other direction is $V_2$.

It is guaranteed that if two line segments intersect, their intersection point is a common endpoint.

Output

Output a single positive integer representing the minimum total activation cost.

Examples

Input 1

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

Output 1

3

Note 1

As shown in the left figure of the example, it is equivalent to the directed graph shown in the right figure. By activating $1 \to 2$ and $2 \to 3$, one can reach regions $2$ and $3$ starting from $1$. Therefore, the minimum total activation cost is $3$.

Constraints

For $60\%$ of the data, the activation costs for both directions of an edge are equal; for $1/2$ of this data, the polygons consist of squares with side length $1$, and the union of all polygons is a rectangle, as shown in the figure below:

For another $20\%$ of the data, the number of regions $\leq 18$.

For another $10\%$ of the data, the number of regions $\leq 150$.

For $100\%$ of the data, $n \leq 3\,000$, the number of regions is at most $1\,000$, the absolute values of point coordinates do not exceed $10\,000$, and the activation cost for each edge does not exceed $100$.