Description

At midnight on Valentine’s Day, Cupid begins his work. He selects an equal number of men and women, senses the “affinity” between every pair of them, and shoots his divine arrows accordingly to make them fall in love. He wants to choose the best plan so that every selected person is shot exactly once, and the sum of the affinities of all chosen pairs is maximized.

However, Cupid’s bow and arrows have limitations. First, the shooting range, though enlarged, is still finite: unlike Yue Lao’s “red thread,” the arrow cannot connect lovers from any distance. Second, regardless of any modifications, an arrow always flies along a straight line. That is, if there is any other person lying on the line segment connecting a man and a woman, Cupid must not shoot that pair—otherwise, as Yue Lao would say, he would be “randomly matching couples.”

Your task is to use a computer to help Cupid find the optimal plan: match the $n$ men to the $n$ women one-to-one to maximize the total affinity, subject to:

• The Euclidean distance between the man and the woman in each chosen pair is at most $k$.
• No other person lies on the line segment between the two in each chosen pair.

Input Format

The first line contains a positive integer $k$, the shooting range of Cupid’s arrow.

The second line contains a positive integer $n$.

Then follow $2 \times n$ lines describing the selected people: the first $n$ lines are men, the last $n$ lines are women.

Each person’s information has two parts: their name and their position. The name is a case-insensitive string of letters with length less than $20$. The position is a pair of integers representing coordinates, separated by a space. The format is: x y Name

The remaining part of the input describes affinities. Each line has the format: Name1 Name2 p

Here, Name1 and Name2 are the names of two people who are “destined,” and $p$ is their affinity value (a positive integer with $p \le 255$).

The input ends with: End

For any pair of people, the affinity is described at most once. If it is not described, their affinity is $1$.

Output Format

Output a single positive integer: the maximum possible sum of affinities over all valid one-to-one matchings. Each selected person must be matched exactly once.

2
3
0 0 Adam
1 1 Jack
0 2 George
1 0 Victoria
0 1 Susan
1 2 Cathy
Adam Cathy 100
Susan George 20
George Cathy 40
Jack Susan 5
Cathy Jack 30
Victoria Jack 20
Adam Victoria 15
End

65

Hint

$1 \le n \le 30$.

CTSC 2000, Round 2.

Translated by ChatGPT 5