직사각형 포장하기

그림 1: 네 직사각형을 배치하는 여섯 가지 기본 형태

네 개의 직사각형이 주어진다. 이 네 직사각형을 서로 겹치지 않게 모두 담을 수 있는, 감싸는 직사각형 중 가장 작은 것을 찾아라. 여기서 "가장 작은"이란 넓이가 최소임을 뜻한다.

네 직사각형은 모두 변이 감싸는 직사각형의 대응하는 변과 평행해야 한다. 그림 1은 네 직사각형을 붙이는 여섯 가지 방법을 보여 준다. 다른 모든 배치는 이 기본 형태를 회전하거나 뒤집어 얻을 수 있으므로, 이 여섯 가지가 유일한 기본 형태이다.

각 직사각형은 $90°$ 회전하여 두 방향 중 어느 쪽으로도 놓을 수 있다. 넓이가 같은 최소 크기의 감싸는 직사각형이 여러 개 존재할 수 있으며, 그러한 직사각형을 모두 구해야 한다.

입력은 네 줄로 이루어진다. 각 줄은 직사각형 하나를 두 양의 정수, 즉 그 직사각형의 두 변의 길이로 나타낸다. 각 변의 길이는 $1$ 이상 $50$ 이하이다.

출력은 해의 개수보다 한 줄 더 많은 줄로 이루어진다. 첫 줄에는 감싸는 직사각형의 최소 넓이(정수 하나)를 출력한다. 이어지는 각 줄에는 해 하나를 두 수 $p$와 $q$($p \le q$)로 출력한다. 이 줄들은 $p$의 오름차순으로 정렬되어야 하며, 모두 서로 달라야 한다.