P1500 [CTT 2000] Cupid's Trouble

As society develops, relationships between people are becoming increasingly utilitarian. Recently, Cupid, the god of love, found that love is no longer entirely pure. This troubled him greatly: it became harder for him to find suitable couples to shoot with his arrows. So Cupid traveled all the way to China to consult Yue Lao (Yuelao), the deity who governs love among Eastern people. Yue Lao told Cupid that pure love does exist; he just had not found it. In the East, people value “fate.” As long as Yue Lao makes a clay man and a clay woman and connects them with a red thread, the people they represent will fall in love—no matter where they are. Cupid’s arrows, however, can only hit two people who are relatively close to each other, which greatly limits his choices and keeps him from finding truly destined couples.

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.

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 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.

$1 \le n \le 30$. CTSC 2000, Round 2. Translated by ChatGPT 5