최강 장비 세트

메이플스토리의 캐릭터는 모두 고유의 스탯 요구치를 가지고 있다. 어떤 캐릭터는 힘, 어떤 캐릭터는 민첩성, 또 어떤 캐릭터는 체력을 우선시할 수 있다. 플레이어는 캐릭터의 스탯 가중치에 따라 최적의 장비 조합을 구성해야 한다.

캐릭터는 무기, 장갑, 상의, 하의, 신발, 벨트, 목걸이, 모자, 반지의 $9$개 부위에 각각 하나씩 장비를 착용할 수 있다. 각 장비는 착용 가능한 부위가 정해져 있으며, 장착 시 정해진 만큼의 STR(힘), DEX(민첩성), HP(체력) 스탯을 얻을 수 있다. 모든 장비는 하나의 세트에만 속한다.

캐릭터가 얻는 스탯은 장착한 장비로부터 얻는 스탯의 합계로 계산되며, 각 스탯(STR, DEX, HP)은 서로 독립적으로 따로따로 합산된다. 즉, STR는 모든 장비의 STR 스탯을 더한 값, DEX는 모든 장비의 DEX 스탯을 더한 값, HP는 모든 장비의 HP 스탯을 더한 값으로 계산된다.

같은 세트의 장비를 여러 개 장착할 경우, 해당 세트의 효과를 추가로 얻을 수 있다. 세트의 효과는 STR, DEX, HP 스탯이 증가하는 값으로 주어진다.

세트 효과는 같은 세트에 속하는 장비를 정해진 수 이상으로 착용할 경우 적용된다. 같은 세트에 속하는 장비를 $3$개, $5$개, $7$개, $9$개 착용할 때마다 세트 효과가 적용된다. 예를 들어, 같은 세트의 장비를 $6$개 장착하면 “$3$세트 효과”와 “$5$세트 효과”를 모두 얻는다. $9$개를 착용하면 $3$, $5$, $7$, $9$개를 착용했을 때의 효과를 모두 누적해서 적용받는다. 세트 효과에 의한 스탯들 역시 STR, DEX, HP 스탯이 독립적으로 합산된다.

캐릭터가 장착한 장비와 세트 효과로부터 얻은 STR 스탯의 총합을 $S$, DEX 스탯의 총합을 $D$, HP 스탯의 총합을 $H$라 하자. 캐릭터의 스탯 가중치가 각각 $w_S$, $w_D$, $w_H$일 때, 최종 스탯 점수는 $S \times w_S + D \times w_D + H \times w_H$로 계산된다.

캐릭터의 스탯 가중치와 착용할 수 있는 장비들의 정보, 각 세트의 효과에 대한 정보가 주어진다. 최종 스탯 점수가 최대가 되도록 각 부위에 착용할 장비를 선택하는 프로그램을 작성하시오.

입력 형식

첫 줄에 STR, DEX, HP 가중치를 나타내는 세 정수 $w_S$, $w_D$, $w_H$가 공백으로 구분되어 주어진다. ($1 \le w_S, w_D, w_H \le 10\,000$)

그다음 줄에 전체 장비 개수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 450$)

그다음 줄부터 $N$개의 줄에 걸쳐 각 장비의 정보가 순서대로 주어진다. 이 중 $i$번째 줄에는 $i$번 장비의 정보를 나타내는 여섯 개 값이 아래와 같은 형식을 따라 공백으로 구분되어 주어진다:

• $\mathrm{slot}_i$ $\mathrm{name}_i$ $s_i$ $d_i$ $h_i$ $\mathrm{set}_i$
  • $\mathrm{slot}_i$: 장착 부위 이름을 나타내는 한글 문자열로, 문제에서 주어진 $9$개의 부위(무기, 장갑, 상의, 하의, 신발, 벨트, 목걸이, 모자, 반지) 중 하나다.
  • $\mathrm{name}_i$: 장비의 이름을 나타내는 길이 $1$ 이상 $12$ 이하의 한글 문자열이다. 각 장비의 이름은 서로 다르다.
  • $s_i$: 장비 착용 시 얻는 STR 스탯을 나타내는 정수다. ($0 \le s_i \le 1\,000$)
  • $d_i$: 장비 착용 시 얻는 DEX 스탯을 나타내는 정수다. ($0 \le d_i \le 1\,000$)
  • $h_i$: 장비 착용 시 얻는 HP 스탯을 나타내는 정수다. ($0 \le h_i \le 1\,000$)
  • $\mathrm{set}_i$: 장비가 속한 세트의 이름을 나타내는 문자열로, 아래에 소개될 $M$개의 세트의 이름 중 하나다.

여기서, 한글 문자열이란 한글 문자로 구성된 문자열을 뜻한다.

그다음 줄에 세트 개수를 나타내는 정수 $M$이 주어진다. ($1 \le M \le 150$)

그다음 줄부터 $5M$개의 줄에 걸쳐 각 세트의 단계별 효과 정보가 차례대로 주어진다. 여기서, 각 세트 정보는 아래와 같은 형식을 따라 다섯 줄로 구성된다:

1. 첫 줄에는 세트의 이름을 나타내는 길이 $1$ 이상 $3$ 이하의 알파벳 대문자로 구성된 문자열이 주어진다. 각 세트의 이름은 서로 다르다.
2. 그다음 줄에는 같은 세트 장비를 $3$개 이상 장착했을 때 얻는 STR, DEX, HP 스탯 증가량의 세 정수가 공백으로 구분되어 주어진다. 각 스탯 증가량은 $0$ 이상 $1\,000$ 이하의 정수이다.
3. 그다음 줄에는 같은 세트 장비를 $5$개 이상 장착했을 때 얻는 STR, DEX, HP 스탯 증가량의 세 정수가 공백으로 구분되어 주어진다. 각 스탯 증가량은 $0$ 이상 $1\,000$ 이하의 정수이다.
4. 그다음 줄에는 같은 세트 장비를 $7$개 이상 장착했을 때 얻는 STR, DEX, HP 스탯 증가량의 세 정수가 공백으로 구분되어 주어진다. 각 스탯 증가량은 $0$ 이상 $1\,000$ 이하의 정수이다.
5. 그다음 줄에는 같은 세트 장비를 $9$개 이상 장착했을 때 얻는 STR, DEX, HP 스탯 증가량의 세 정수가 공백으로 구분되어 주어진다. 각 스탯 증가량은 $0$ 이상 $1\,000$ 이하의 정수이다.

출력 형식

첫 줄에 얻을 수 있는 최종 점수의 최댓값을 출력한다.

그다음 줄부터 $9$개의 줄에 걸쳐, 해당 최댓값을 달성하기 위해 각 슬롯에 장착하여야 하는 아이템의 번호를 무기, 장갑, 상의, 하의, 신발, 벨트, 목걸이, 모자, 반지 슬롯 순서로 출력한다.

예제

4 3 5
10
무기 엔젤소드 20 15 10 C
장갑 월묘견장 10 20 5 A
상의 수수한무사상의 15 5 20 B
하의 파란청반바지 5 25 10 C
신발 수수한무사신발 10 5 15 B
벨트 황금돼지허리띠 25 5 5 A
목걸이 아울펜던트 15 0 10 A
모자 블랙윙의모자 5 15 10 C
반지 파란말풍선반지 5 5 12 A
반지 레지스탕스링 5 20 3 B
3
A
10 0 0
0 10 0
0 0 10
5 5 5
B
8 8 0
0 0 12
10 0 10
0 10 10
C
0 12 0
0 0 12
0 10 5
10 10 0

1342
1
2
3
4
5
6
7
8
10

채점 방식

이 문제는 풀이 소스 코드를 제출하지 않고, 각 테스트 케이스의 입력 데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

이 문제의 총점은 모든 미션의 점수의 합으로 계산된다. 각 미션의 점수를 계산하는 방법은 다음과 같다.

• $Q$: 미션의 만점
• $K$: 미션에 대한 참가자의 점수
• $\alpha$: 미션마다 정해진 상수
• $\beta$: 참가자가 구성한 해로 얻는 스탯 최종점수

이때, 미션에 대한 참가자의 점수 $K$는 $\displaystyle Q \times \left(\frac{\beta}{\alpha}\right)^2$ 을 $0.1$ 단위로 버림한 값이다.

단, 참가자의 출력이 올바르지 않은 경우 (출력 형식을 맞추지 않았거나, 제약 조건을 지키지 않는 등) $K = 0$이다.

각 미션의 정보는 다음과 같다.

미션마다 만점을 받을 수 있는 출력이 존재함이 보장된다.

해설