남은 피자 안전하게 쌓기

Rafael과 룸메이트들은 피자를 아주 좋아하지만 예산이 빠듯해서, 학기 동안 매일 정확히 같은 양의 피자를 먹기로 했습니다. 기간은 최대 100일 연속입니다. 학기 첫날부터 Ultracheap Pizza Express에서 싸고 맛있는 피자 여러 종류를 주문합니다. 예를 들어 Pepperoni, Sausage & Mushroom, Veggie를 주문할 수 있습니다. 가게는 피자를 조각내 주지 않기 때문에, Rafael이 계획에 따라 각 피자를 직접 자릅니다. 예를 들어 Pepperoni는 8조각, Sausage는 7조각, Veggie는 11조각으로 자를 수 있습니다. 그다음 따뜻한 조각을 먹는데, 예를 들어 Pepperoni 1조각, Sausage 1조각, Veggie 2조각을 합쳐서 먹습니다. 마지막으로 남은 피자를 원래 상자에 담은 채 선반이 없는 싸고 차가운 냉장고에 쌓아 둡니다. 이 작은 냉장고에는 피자 더미를 하나만 넣을 수 있고, 여러 더미로 나눠 넣을 수는 없습니다.

그 이후 매일 냉장고에서 더미 전체를 꺼내 상자를 열고, 첫날 정한 것과 똑같은 수의 조각을 각 피자에서 먹습니다. 차갑게 먹거나 싸고 따뜻한 전자레인지에 데워 먹습니다. 매일 먹고 나서 남은 피자는 다시 냉장고에 넣되, 이전과 정확히 같은 순서로 쌓습니다. 왜 이렇게 꼼꼼하게 쌓느냐고요? Ultracheap은 상자에 라벨을 붙이지 않아서, 순서를 일정하게 유지해야만 상자를 계속 열어 보지 않고도 피자를 구별할 수 있기 때문입니다.

피자가 거의 떨어지면, 그날그날 먹는 피자 종류별 양이 항상 정확히 같도록 대체 피자를 주문합니다. 새 통피자는 그날 먹을 조각을 자르기 직전에 도착하므로, 냉장고에 통째로 남은 피자가 생기는 일은 없고 피자가 모자라는 일도 없습니다. 빈 상자는 남은 피자가 아니므로 버립니다. 어떤 종류의 피자가 남지 않은 날에도, 남은 피자는 첫날과 같은 상대적 순서로 쌓입니다. 예를 들어 위에서부터 Veggie, Pepperoni, 맨 아래 Sausage 순서로 쌓기로 했는데, 남은 것을 넣을 때 Pepperoni 상자가 비어 있다면, Veggie 상자는 Sausage 상자 바로 위에 쌓입니다. 다음 날 새 Pepperoni 상자가 도착하면, 세 상자는 다시 첫날의 순서를 유지합니다.

쌓을 때 문제가 하나 있습니다. 판지 상자가 아주 싸다는 것입니다. 상자가 무너져 피자 위로 내려앉으면 피자는 망가지기 마련입니다. 판지 맛이 나는 모차렐라라니... 으웩!

Rafael은 한 피자가 다른 피자를 짓누르는 위험을 줄이려고, 가장 가벼운 상자부터 가장 무거운 상자 순으로, 무거운 남은 피자를 아래에 두고 쌓자는 기발한 생각을 했습니다. 처음에는 모든 피자의 무게가 같으므로, 상자에 남은 피자의 비율을 계산하면 남은 피자의 무게를 예측할 수 있습니다. 위 예에서 첫날 남은 피자는 Pepperoni 7/8, Sausage 6/7, Veggie 9/11이므로, 아래에서부터 Pepperoni, Sausage, 맨 위에 Veggie 순으로 쌓아야 합니다.

룸메이트 Robin은 Rafael의 계획이 첫날에는 잘 작동하지만, 피자마다 소비 속도가 다르다고 지적합니다. 남은 피자를 항상 같은 순서로 쌓다 보면, 무거운 피자가 가벼운 피자 위에 올라가 피자가 망가질 위험이 생길 수 있습니다. 앞의 예를 이어 가 보면, 6일째에 쌓아야 할 남은 피자는 Pepperoni 2/8, Sausage 1/7, Veggie 10/11입니다. Pepperoni 남은 피자는 가벼운 Sausage 아래에 제대로 놓이지만, Veggie가 맨 위에 있고 이제 가장 무거워졌습니다. 이러면 Sausage 남은 피자가 위험해집니다.

주문한 피자 목록과 각 피자의 소비 속도가 주어질 때, 매일 사용할 수 있으면서 판지와 치즈가 망가질 가능성을 가장 낮추는 남은 피자의 쌓는 순서를 정하세요.

첫 줄에는 평가할 학기 계획의 개수를 나타내는 양의 정수 N이 주어집니다. 각 학기 계획은 주문할 피자의 총 종류 수 P (2 ≤ P ≤ 5)와, 계획 기간을 나타내는 일수 D (1 ≤ D ≤ 100)를 공백으로 구분한 줄로 시작합니다. Rafael이 피자를 끊고 Paleo 식단으로 바꿀 수도 있으므로 D는 이런 식으로 주어집니다. 이어지는 2×P줄에는 각 피자를 정확히 두 줄씩 설명합니다.

각 피자 설명의 첫 줄에는 피자 종류를 나타내는 1자 이상 20자 이하의 영어 소문자가 주어집니다. 이름은 학기 계획 안에서 서로 달라야 합니다. 둘째 줄에는 정수 E (1 ≤ E < 20)와 S (E < S ≤ 20)가 공백으로 구분되어 주어집니다. 여기서 E는 그 종류의 피자를 매일 먹는 조각 수이고, S는 그 종류의 통피자 한 판의 전체 조각 수입니다. 입력에는 빈 줄이나 불필요한 공백이 없습니다.

입력의 각 학기 계획에 대해, "Leftover Pizza Stacking Order for Semester M:" 줄을 출력합니다. 여기서 M은 입력에서 학기 계획의 번호이며 1부터 셉니다. 다음 줄부터 그 학기 계획의 피자 종류 이름 P개를 한 줄에 하나씩, 위에서 아래로 쌓아야 하는 순서대로 출력합니다. 쌓는 순서는 가능한 가장 안전한 순서여야 합니다. 즉, D일 동안 무거운 피자가 가벼운 피자 바로 위에 쌓이는 경우의 수를 최소화해야 합니다. 같은 날 같은 더미에서 이런 경우가 여러 번 나타날 수 있으며, 각 경우가 모두 합계에 포함됩니다. 마지막 날 이후의 쌓기 상태도 확인하여 합계에 포함해야 합니다.

가장 안전한 쌓기 순서가 여럿이면, 더미의 위에서 아래로 피자 이름을 비교했을 때 사전순으로 가장 앞서는 순서를 출력합니다. 각 학기 계획의 출력 뒤에는 빈 줄을 한 줄 남깁니다. 출력 형식은 샘플 출력에 나온 형식을 따릅니다.