31594번 - Attraction Score 다국어

문제

There are $n$ cities, numbered from 1ドル$ to $n,ドル in the fictional country of Manteiv. We can consider these cities to be on a flat plane with a 2D coordinate system, where city i is at coordinates $(x_i , y_i)$. No two cities are located at the same position.

There are $m$ highways, numbered from 1ドル$ to $m,ドル each of which is a line segment with two different cities as its endpoints and has a number of attraction points alongside it. Specifically, highway $j$ has $a_j$ attraction points and connects cities $u_j$ and $v_j $as its endpoints. Having intersections on highways causes traffic jams, and building a highway on top of another highway costs a lot of money. Therefore, it is guaranteed that

• no two highways intersect at any point other than at a city,
• no highway passes through a city other than its two endpoints, and
• there is at most one highway connecting each pair of cities.

The Manteiv Ministry of Tourism would like to choose a subset of cities as tourist attractions. Intuitively, the ministry would like many pairs of chosen cities to be connected by a highway with many attraction points. Formally, the attraction score of a non-empty subset of cities $S$ is defined as follows:

• For every pair of integers $(a, b)$ where $a < b,ドル cities $a$ and $b$ are in $S,ドル and they are connected by a highway, add the number of attraction points on the highway to the score.
• Let $f(S)$ be the number of pairs of integers $(a, b)$ where $a < b,ドル cities $a$ and $b$ are in $S,ドル and they are not connected by a highway. The score incurs a penalty (negative) score of 10ドル^6$ multiplied by the square of $f(S)$. In other words, subtract 10ドル^6 × f(S)^2$ from the score.

For example, let $n = 3,ドル cities 1ドル$ and 2ドル$ be connected by a highway with 10ドル$ attraction points, cities 2ドル$ and 3ドル$ be connected by a highway with 20ドル$ attraction points, and cities 1ドル$ and 3ドル$ not be connected by a highway.

• The attraction score of the subset of cities $\{1\}$ is 0ドル$.
• The attraction score of the subset of cities $\{1, 2\}$ is 10ドル - 10^6 \times 0^2 = 10$.
• The attraction score of the subset of cities $\{2, 3\}$ is 20ドル - 10^6 \times 0^2 = 20$.
• The attraction score of the subset of cities $\{1, 2, 3\}$ is 10ドル + 20 - 10^6 \times 1^2 = -999,円 970$.

As an advisor to the ministry, you would like to find the maximum attraction score among all possible non-empty subsets of cities $S$.

입력

The first line of input contains two integers $n$ and $m$ (1ドル ≤ n ≤ 100,円 000$; 0ドル ≤ m ≤ 300,円 000$). Each of the next $n$ lines contains two integers. The $i$-th line contains $x_i$ and $y_i$ (0ドル ≤ x_i , y_i ≤ 10^9$). Each of the next $m$ lines contains three integers. The $j$-th line contains $u_j,ドル $v_j,ドル and $a_j$ (1ドル ≤ u_j < v_j ≤ n$; 0ドル ≤ a_j ≤ 10^6$). The highways are guaranteed to satisfy the conditions in the problem statement.

출력

Output an integer representing the maximum attraction score among all possible non-empty subsets of cities $S$.

제한

힌트