Song Contest

Every year, the continent of Cacophonea holds the Cacophonean Song Contest. Each of its nations presents an act performed by a national singer or group. Every inhabitant may televote for any act that is not from their own nation, so a nation never votes for its own act.

In the end, each of the $s$ participating nations awards points to $r$ acts. From a given nation, the act with the most votes receives $r$ points, the act with the second-most votes receives $r-1$ points, and so on, so that the act with the $r$-th most votes receives $1$ point; less popular acts receive no points from that nation. The final ranking of the contest is decided by the total number of points each nation receives.

Music producer Dustin has followed the contest for years and has noticed that some nations televote for political rather than artistic reasons:

• A politically voting nation prefers acts from nearby nations. Its measure of popularity is the Euclidean distance between its own capital and the other nation's capital, regardless of artistic quality. The nation with the closest capital receives the most votes, and the nation with the farthest capital receives the fewest — possibly no points at all when $r < s - 1$. No two capitals are ever at exactly the same distance from a given capital.
• A quality-motivated nation awards points strictly according to an undisputed ranking of the acts by artistic quality. This ranking has no ties, so every nation has a unique rank.

Dustin knows a trick no other producer knows: an artist can win the favour of a politically voting nation by giving it special attention during the act (for example, singing parts in its local dialect or waving its flag). The more attention a politically voting nation receives, the higher it ranks the performer — but this comes at the expense of the original act and makes quality-motivated nations rank it lower.

Concretely, Dustin can split an act into exactly $s - 1$ parts. Initially every part is dedicated to the performer's own nation (reflecting the original artistic idea), but this can be changed:

• For each part dedicated to a particular politically voting nation, that nation ranks the performer's nation one place higher (unless it is already ranked first). Because each ranking position is unique, the nation previously at that higher position moves down one place.
• Quality-motivated nations dislike such pandering. For each part dedicated to any nation other than the performer's own, every quality-motivated nation ranks the performer's nation one place lower (unless it is already ranked last).

Only the number of parts dedicated to a nation affects the voting; the order of the parts within the act does not matter.

Dustin wants to design an act that earns as many points as possible in the overall result. Determine the largest overall point total he can obtain when he uses these act-changing tactics optimally.

• The first line contains an integer $n$, the number of test cases.
• Then, for each test case:
  • A line with an integer $s$ ($1 < s \le 100$), the number of participating nations.
  • Then, for each nation:
    • A line with the nation's name $c$ (a string containing no spaces; names are unique within a test case), followed by a space and a single character describing its voting behaviour: q if quality-motivated, p if politically motivated.
    • A line with the integer coordinates $x$ and $y$ of the nation's capital ($-10000 \le x \le 10000$, $-10000 \le y \le 10000$), separated by a space, followed by the artistic quality rank $q$ of its act — a unique integer in the range $1 \ldots s$.
  • A line with an integer $r$ ($0 < r \le s - 1$), the number of nations each nation awards points to.
  • A line with the name of the nation for which Dustin should produce the act so as to maximize its points.

For each test case, print a single line containing one integer: the maximum overall score the act can achieve when the act-changing tactics are used optimally.