흐름 배치

흐름 배치 관리자는 직사각형 객체들을 직사각형 창 안에 왼쪽에서 오른쪽 순서로 한 줄씩 채워 넣는다. 현재 줄의 남은 공간에 다음 직사각형이 들어가지 못하면, 그 직사각형은 지금까지 놓인 모든 직사각형 아래의 새 줄 왼쪽 끝으로 내려가고, 거기서부터 다시 왼쪽에서 오른쪽으로 채우기가 이어진다.

여러 직사각형의 크기와 창의 최대 너비가 주어질 때, 모든 직사각형을 배치한 뒤 최종 창의 크기를 구하는 프로그램을 작성하라.

창의 너비는 가장 넓은 줄의 너비(그 줄에 놓인 직사각형들의 너비 합)와 같고, 창의 높이는 각 줄 높이의 합과 같다. 이때 한 줄의 높이는 그 줄에서 가장 높은 직사각형의 높이이다.

예를 들어 최대 너비가 35인 창에 크기가 각각 10 x 5, 20 x 12, 8 x 13인 직사각형 세 개가 주어지면, 앞의 두 직사각형은 첫 번째 줄에 함께 놓이고(10 + 20 = 30 ≤ 35), 세 번째 직사각형은 두 번째 줄을 시작한다(30 + 8 = 38 > 35). 최종 창의 크기는 30 x 25이다. 너비는 10 + 20 = 30이고 높이는 12 + 13 = 25이기 때문이다.

입력은 하나 이상의 데이터 집합으로 이루어지며, 마지막 줄에는 0 하나만 주어진다.

각 데이터 집합은 창의 최대 너비를 나타내는 정수 m ($1 \le m \le 80$)이 적힌 줄로 시작한다. 그 뒤로 직사각형의 크기를 나타내는 줄이 1개 이상 15개 이하로 이어지며, 각 줄에는 직사각형의 너비가 먼저, 그다음 높이가 적혀 있다. 직사각형 목록의 끝은 -1 -1 쌍으로 표시되며, 이 쌍은 실제 직사각형이 아니다.

각 직사각형의 너비는 1 이상 80 이하, 높이는 1 이상 100 이하이다.

각 데이터 집합에 대해, 최종 창의 너비, 공백 한 칸, 소문자 x, 공백 한 칸, 최종 창의 높이를 차례로 출력한다.