1차원 공간에서의 선분,

2차원 공간에서의 직사각형,

3차원 공간에서의 직육면체를 생각해 보자.

선분의 크기는 변수 A로,

직사각형의 크기는 두 개의 변수 A와 B로,

직육면체의 크기는 세 개의 변수 A, B, C로 표현할 수 있다.

선분에 길이는 A, 직사각형의 넓이는 A*B, 직육면체의 부피는 A*B*C이다.

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

4차원 초직사각형의 부피는 A*B*C*D이다.

처음에 변수 A의 값은 A₀, 변수 B의 값은 B₀, 변수 C의 값은 C₀, 변수 D의 값은 D₀이다.

이 초직사각형의 크기를 바꿀 수 있는 카드가 N장 있다.

이 중 i(1 ≤ i ≤ N)번째 카드에는 문자 T_i와 자연수 U_i가 적혀 있다.

T_i는 A, B, C, D중 하나이며, 값을 바꿀 변수의 이름을 의미한다.

i번재 카드를 사용하면, T_i에 해당하는 변수의 값이 U_i만큼 증가한다.

사용한 카드는 즉시 소멸하므로 각각의 카드는 최대 한 번씩만 사용할 수 있다.

당신은 4차원 초직사각형의 부피를 최대화하고자 하며,

이를 위해 주어진 카드 중 정확히 K장을 골라서 원하는 순서대로 사용할 수 있다.

어떤 카드를 순서대로 사용해야 하는지를 구하여 출력하는 프로그램을 작성하라.

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

초직사각형 timer 1s memory 512MB

초직사각형 1s 512MB