MBTI 궁합을 이용한 조 구성

다오 선생님은 학생 두 명이 한 조를 이루게 한 후, 조별 과제를 주는데 같은 조 학생들이 자주 싸우는 것을 목격했다. 어떻게 하면 학생들이 덜 싸우고 행복한 분위기에서 조별 과제를 진행할 수 있을까 고민했고, MBTI 궁합이 잘 맞는 학생들 사이에는 싸움이 적게 일어나는 것을 확인했다.

그래서 다오 선생님은 MBTI를 활용하여 조를 짜기로 계획하였다.

MBTI는 다음과 같은 $4$가지 분류 기준에 따른 결과에 의해 학생들을 $16$가지 심리 유형 중의 하나로 분류한다.

1. 정신적 에너지의 방향성을 나타내는 지표: 외향(E)-내향(I)
2. 정보 수집을 포함한 인식의 기능을 나타내는 지표: 감각(S)-직관(N)
3. 수집한 정보를 토대로 합리적으로 판단하고 결정 내리는 지표: 사고(T)-감정(F)
4. 인식 기능과 판단 기능이 실생활에서 적용되어 나타난 생활 양식을 보여 주는 지표: 판단(J)-인식(P)

각 학생의 성향은 네 가지 분류 기준 각각에서 하나의 지표를 나타내는 문자의 조합 즉, 길이가 $4$인 문자열로 표현되며, 각 분류 기준의 순서를 따라 해당 지표를 나타내는 문자로 표현된다. 예를 들어, ENFP, INTJ, ESFP 형식으로 표현한다. 하지만,
분류 기준의 순서가 섞인 NIPF 같은 문자열은 사용하지 않는다.

각 분류 기준에 대해 반대되는 성향을 가진 학생들이 같은 조에 있으면 싸움이 일어날 확률이 높기 때문에 다오 선생님은 최대한 비슷한 성향을 가진 학생들끼리 조를 구성하려고 한다.

$4$가지 분류 기준 각각에 대해 성향 차이를 나타내는 정수가 주어진다. 즉, $1$ 이상 $4$ 이하인 $i$에 대해 $i$ 번째 분류 기준에서 성향 차이를 나타내는 $w_i$가 주어진다. 예를 들어, $w_1$은 외향(E)과 내향(I)의 성향 차이, $w_2$는 감각(S)과 직관(N)의 성향 차이를 나타낸다.

한 조가 된 두 학생의 MBTI 분류 기준이 모두 일치하면 두 학생의 성향 차이 점수는 $0$이 되지만, 그렇지 않은 경우 서로 일치되지 않은 분류 기준에 대해서 분류 기준의 성향 차이의 합이 그 조의 성향 차이 점수가 된다.

$N$ 명의 학생으로 구성된 $\frac{N}{2}$ 개 조의 성향 차이 점수 합이 최소가 되도록 조를 만드는 프로그램을 작성하시오.

입력 형식

첫 줄에 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다. ($1 \le T \le 10$)

각 테스트 케이스의 첫 줄엔 학생들의 수를 나타내는 정수 $N$과 $4$가지 MBTI 분류 기준 각각에 대한 성향 차이 $w_i$가 주어진다. ($2 \le N \le 500;$ $1 \le w_i \le 1\,000\,000\,000;$ $N$은 짝수)

두 번째 줄에는 각 학생의 MBTI를 나타내는 길이 $4$인 문자열이 $N$ 개 주어진다. 주어지는 문자열에서 모든 문자는 알파벳 대문자이다.

출력 형식

각 테스트 케이스에 대해, 모든 조의 성향 차이 점수 합의 최솟값을 나타내는 정수를 각 줄에 출력한다.

예제

2
2 4 3 2 1
INFP ESFJ
4 1 2 3 4
ISFP ENTJ ENFJ INFP

8
5

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설