초직사각형

1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자.

선분의 크기는 변수 $ A $로, 직사각형의 크기는 두 개의 변수 $ A $와 $ B $로, 직육면체의 크기는 세 개의 변수 $ A $, $ B $, $ C $로 표현할 수 있다. 선분의 길이는 $ A $, 직사각형의 넓이는 $ A \cdot B $, 직육면체의 부피는 $ A \cdot B \cdot C $이다.

4차원 공간에 네 개의 변수 $ A $, $ B $, $ C $, $ D $로 크기를 표현할 수 있는 *초직사각형*이 있다. 4차원 초직사각형의 부피는 $ A \cdot B \cdot C \cdot D $이다.

처음에 변수 $ A $의 값은 $ A_0 $, 변수 $ B $의 값은 $ B_0 $, 변수 $ C $의 값은 $ C_0 $, 변수 $ D $의 값은 $ D_0 $이다.

이 초직사각형의 크기를 바꿀 수 있는 카드가 $ N $장 있다. 이 중 $ i $ ($ 1 \le i \le N $)번째 카드에는 문자 $ T_i $와 자연수 $ U_i $가 적혀 있다. $ T_i $는 A, B, C, D 중 하나이며, 값을 바꿀 변수의 이름을 의미한다. $ i $번째 카드를 사용하면, $ T_i $에 해당하는 변수의 값이 $ U_i $만큼 증가한다. 사용한 카드는 즉시 소멸하므로, 각각의 카드는 최대 한 번씩만 사용할 수 있다.

당신은 4차원 초직사각형의 부피를 최대화하고자 하며, 이를 위해 주어진 카드 중 정확히 $ K $장을 골라서 원하는 순서대로 사용할 수 있다. 어떤 카드를 어떤 순서대로 사용해야 하는지를 구하여 출력하는 프로그램을 작성하라.

부피를 최대화하는 사용 방법이 여러 가지 있을 경우 그 중 하나만 구하여 출력하면 된다.

• 주어지는 모든 수는 정수이다.
• $ 1 \le K \le N \le 200\,000 $
• $ 1 \le A_0, B_0, C_0, D_0 \le 1\,000\,000 $
• 모든 $ 1 \le i \le N $에 대해, $ T_i $는 A, B, C, D 중 하나이다.
• 모든 $ 1 \le i \le N $에 대해, $ U_i $는 $ 1 $ 이상 $ 1\,000\,000 $ 이하의 자연수이다.

1. (8점)

   • $ N \le 10 $

     • $ A_0, B_0, C_0, D_0 \le 10 $
     • 모든 $ 1 \le i \le N $에 대해 $ U_i \le 10 $이다.

2. (6점)

   • $ B_0 = C_0 = D_0 = 1 $

     • 모든 $ 1 \le i \le N $에 대해 $ T_i $는 A이다.

3. (15점)

   • $ N \le 300 $

     • $ A_0, B_0, C_0, D_0 \le 100 $
     • 모든 $ 1 \le i \le N $에 대해 $ U_i \le 100 $이다.

4. (21점)

   • 모든 $ 1 \le i \le N $에 대해 $ U_i = 1 $이다.

5. (20점)

   • $ D_0 = 1 $

     • 모든 $ 1 \le i \le N $에 대해 $ T_i $는 A, B, C 중 하나이다.
     • 모든 $ 1 \le i \le N $에 대해 $ U_i \le 10 $이다.

6. (30점)

   • 추가 제약 조건 없음.

첫 번째 줄에 두 개의 정수 $ N $과 $ K $가 공백 하나를 사이로 두고 주어진다.

두 번째 줄에 네 개의 정수 $ A_0 $, $ B_0 $, $ C_0 $, $ D_0 $가 공백 하나씩을 사이로 두고 주어진다.

다음 $ N $개의 줄에는 카드들에 대한 정보가 주어진다. 이 중 $ i $ ($ 1 \le i \le N $)번째 줄에는 $ T_i $와 $ U_i $가 공백 하나를 사이로 두고 주어진다.

$ K $개의 줄에 선택한 카드들을 사용할 순서대로 입력 형식과 같은 방식으로 한 줄에 한 카드씩 출력한다.