노래 경연 대회

매년 카코포네아(Cacophonea) 대륙에서는 카코포네아 노래 경연 대회가 열립니다. 각 나라는 자국의 가수나 그룹이 선보이는 무대(act) 하나를 출품합니다. 모든 주민은 자기 나라의 무대가 아닌 무대에 한해 전화 투표를 할 수 있으므로, 어떤 나라도 자국의 무대에는 투표할 수 없습니다.

최종적으로 $s$개 참가국은 각각 $r$개의 무대에 점수를 줍니다. 한 나라 기준으로, 표를 가장 많이 받은 무대는 $r$점, 두 번째로 많이 받은 무대는 $r-1$점을 받는 식으로 이어져, $r$번째로 많은 표를 받은 무대는 $1$점을 받습니다. 그보다 인기가 낮은 무대는 그 나라로부터 점수를 받지 못합니다. 대회의 최종 순위는 각 나라가 받은 총점으로 결정됩니다.

음악 프로듀서 더스틴(Dustin)은 오랫동안 이 대회를 지켜봐 왔고, 일부 나라가 예술적 이유가 아니라 정치적 이유로 투표한다는 사실을 알아차렸습니다.

• 정치적으로 투표하는 나라는 가까운 나라의 무대를 선호합니다. 인기의 척도는 예술성과 무관하게 자국 수도와 상대국 수도 사이의 유클리드 거리입니다. 수도가 가장 가까운 나라가 표를 가장 많이 받고, 수도가 가장 먼 나라가 표를 가장 적게 받습니다($r < s - 1$이면 점수를 아예 못 받을 수도 있습니다). 한 수도를 기준으로 두 나라의 수도까지의 거리가 같은 경우는 절대 없습니다.
• 예술성을 중시하는 나라는 예술적 품질에 따른 이견 없는 순위에 따라 엄격하게 점수를 줍니다. 이 순위에는 동점이 없으므로 각 나라는 고유한 등수를 가집니다.

더스틴은 다른 프로듀서가 모르는 요령을 알고 있습니다. 아티스트는 무대에서 특정 나라에 특별한 관심을 보임으로써(예: 그 나라 방언으로 일부를 부르거나 국기를 흔드는 등) 정치적으로 투표하는 나라의 호감을 살 수 있습니다. 정치적으로 투표하는 나라가 그런 관심을 많이 받을수록 그 나라는 공연자를 더 높은 등수로 매깁니다. 물론 이는 본래 무대의 완성도를 희생하는 것이어서, 예술성을 중시하는 나라는 이런 행동에 벌을 줍니다.

구체적으로 더스틴은 하나의 무대를 정확히 $s - 1$개의 부분으로 나눌 수 있습니다. 처음에는 모든 부분이 공연자 자국(원래의 예술적 의도)에 바쳐지지만, 이는 다음과 같이 바꿀 수 있습니다.

• 특정 정치적 투표 국가에 바쳐진 부분 하나마다, 그 나라는 공연자의 나라를 한 등수 위로 올립니다(이미 1등이면 그대로입니다). 각 등수 자리는 고유하므로, 원래 그 위 자리에 있던 나라는 한 등수 아래로 내려갑니다.
• 예술성을 중시하는 나라는 이런 아부를 싫어합니다. 공연자 자국이 아닌 어떤 나라에 바쳐진 부분 하나마다, 모든 예술성 중시 국가는 공연자의 나라를 한 등수 아래로 내립니다(이미 꼴찌면 그대로입니다).

투표에 영향을 주는 것은 각 나라에 몇 개의 부분을 바쳤는지뿐이며, 무대 안에서 부분들의 순서는 중요하지 않습니다.

더스틴은 전체 결과에서 최대한 많은 점수를 얻는 무대를 만들고자 합니다. 위에서 설명한 무대 변경 전술을 최적으로 사용할 때 그가 얻을 수 있는 전체 최고 점수를 구하세요.

• 첫 번째 줄에는 테스트 케이스의 개수 정수 $n$이 주어집니다.
• 그다음, 각 테스트 케이스마다:
  • 참가국 수를 나타내는 정수 $s$ ($1 < s \le 100$)가 한 줄에 주어집니다.
  • 그다음, 각 나라마다:
    • 나라 이름 $c$(공백이 없는 문자열이며, 한 테스트 케이스 안에서 이름은 서로 다릅니다), 공백, 그리고 투표 성향을 나타내는 한 글자가 한 줄에 주어집니다. 예술성을 중시하면 q, 정치적 성향이면 p입니다.
    • 나라 수도의 정수 좌표 $x$와 $y$($-10000 \le x \le 10000$, $-10000 \le y \le 10000$)가 공백으로 구분되어 주어지고, 이어서 그 무대의 예술적 품질 등수 $q$가 한 줄에 주어집니다. $q$는 $1 \ldots s$ 범위의 서로 다른 정수입니다.
  • 각 나라가 점수를 주는 나라의 수를 나타내는 정수 $r$ ($0 < r \le s - 1$)이 한 줄에 주어집니다.
  • 더스틴이 점수를 최대화하도록 무대를 만들어야 할 나라의 이름이 한 줄에 주어집니다.

각 테스트 케이스마다, 무대 변경 전술을 최적으로 사용했을 때 무대가 얻을 수 있는 전체 최고 점수를 정수 하나로 한 줄에 출력합니다.