직사각형 그림

직사각형 그림은 다음 조건을 모두 만족하는, 축에 평행한 여러 개의 직사각형으로 이루어진다.

1. 임의의 두 직사각형은 서로 포함 관계(하나가 다른 하나의 내부에 완전히 들어감)이거나, 서로 겹치지 않는다.
2. 모든 직사각형의 변은 x축과 y축에 평행하다.
3. 임의의 두 직사각형의 변은 서로 최소 $d$만큼 떨어져 있으며, 한 직사각형이 다른 직사각형을 포함하는 경우에도 이 조건이 성립한다.
4. 직사각형 $R$을 포함하는 가장 작은 직사각형을 그 직사각형의 상위 직사각형이라 한다. 같은 상위 직사각형을 가지는 직사각형들을 동료 직사각형이라 하며, 하나의 상위 직사각형 아래의 동료 직사각형들은 한 줄로 배치된다. 즉 가로로(아래 변이 일직선 위에 놓이도록) 배치되거나 세로로(왼쪽 변이 일직선 위에 놓이도록) 배치된다.
5. 내부에 다른 직사각형을 포함하지 않는 직사각형을 사진 직사각형이라 하며, 정해진 크기의 사진으로 채워진다.
6. 상위 직사각형이 없는 직사각형은 정확히 하나이며, 이를 루트 직사각형이라 한다.
7. 모든 꼭짓점의 좌표는 정수이다.

사진 직사각형의 크기와 방향은 주어지며 바꿀 수 없다. 각 동료 직사각형 그룹마다 가로로 배치할지 세로로 배치할지를 독립적으로 선택할 수 있다. 루트 직사각형의 넓이가 최소가 되도록 이 방향들을 정하고, 그 최소 넓이를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $d$가 주어진다($1 \le n \le 100$, $0 \le d \le 30$). 여기서 $n$은 직사각형의 개수이다.

이어지는 $n$개의 줄은 직사각형을 설명하며, 그중 $i$번째 줄은 id가 $i$인 직사각형을 설명한다. 루트 직사각형의 id는 항상 $1$이다. 상위 직사각형이 직사각형 $i$인 직사각형들의 id 집합을 $R_i$라 하자.

• $R_i$가 비어 있지 않으면, 그 줄은 k(= $|R_i|$)에 이어 $R_i$의 원소 k개가 공백으로 구분되어 주어진다.
• 그렇지 않으면 직사각형 $i$는 사진 직사각형이며, 줄은 0 a b 형태이다. 여기서 $1 \le a \le 30$과 $1 \le b \le 30$은 각각 x축 방향과 y축 방향 변의 길이이다.

입력의 끝은 0 0만 있는 줄로 표시된다.

각 테스트 케이스마다, 동료 직사각형 그룹들의 가로/세로 방향을 모두 고려했을 때 가능한 루트 직사각형의 최소 넓이를 한 줄에 출력한다.

예제 답을 만드는 배치의 한 예시: