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의 값은 A0, 변수 B의 값은 B0, 변수 C의 값은 C0, 변수 D의 값은 D0이다.
이 초직사각형의 크기를 바꿀 수 있는 카드가 N장 있다. 이 중 i (1 ≤ i ≤ N)번째 카드에는 문자 Ti 와 자연수 Ui가 적혀 있다. Ti는 A, B, C, D 중 하나이며, 값을 바꿀 변수의 이름을 의미한다. i번째 카드를 사용하면, Ti에 해당하는 변수의 값이 Ui만큼 증가한다. 사용한 카드는 즉시 소멸하므로, 각각의 카드는 최대 한 번씩만 사용할 수 있다.
당신은 4차원 초직사각형의 부피를 최대화하고자 하며, 이를 위해 주어진 카드 중 정확히 K장을 골라서 원하는 순서대로 사용할 수 있다. 어떤 카드를 어떤 순서대로 사용해야 하는지를 구하여 출력하는 프로그램을 작성하라.
부피를 최대화하는 사용 방법이 여러 가지 있을 경우 그 중 하나만 구하여 출력하면 된다.

첫 번째 줄에 두 개의 정수 N과 K가 공백 하나를 사이로 두고 주어진다. 
두 번째 줄에 네 개의 정수 A0, B0, C0, D0가 공백 하나씩을 사이로 두고 주어진다. 
다음 N개의 줄에는 카드들에 대한 정보가 주어진다. 이 중 i (1 ≤ i ≤ N)번째 줄에는 Ti와 Ui가 공백 하나를 사이로 두고 주어진다. 
• 주어지는 모든 수는 정수이다. 
• 1 ≤ K ≤ N ≤ 200 000 
• 1 ≤ A0, B0, C0, D0 ≤ 1 000 000 
• 모든 1 ≤ i ≤ N에 대해, Ti는 A, B, C, D 중 하나이다. 
• 모든 1 ≤ i ≤ N에 대해, Ui는 1 이상 1 000 000 이하의 자연수이다. 
(테스트 케이스 비율)
1. (8점)
 • N ≤ 10 • A0, B0, C0, D0 ≤ 10 
 • 모든 1 ≤ i ≤ N에 대해 Ui ≤ 10이다. 
2. (6점) 
 • B0 = C0 = D0 = 1 
 • 모든 1 ≤ i ≤ N에 대해 Ti는 A이다. 
3. (15점)
 • N ≤ 300 • A0, B0, C0, D0 ≤ 100
 • 모든 1 ≤ i ≤ N에 대해 Ui ≤ 100이다. 
4. (21점)
 • 모든 1 ≤ i ≤ N에 대해 Ui = 1이다. 
5. (20점)
 • D0 = 1
 • 모든 1 ≤ i ≤ N에 대해 Ti는 A, B, C 중 하나이다.
 • 모든 1 ≤ i ≤ N에 대해 Ui ≤ 10이다. 
6. (30점)
 • 추가 제약 조건 없음. 

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

	작성자	제목(댓글)
글이 없습니다.

문제 게시판

새 글 작성

2021KOI고등1차