Rectangular Painting

A rectangular painting is made of several axis-aligned rectangles that satisfy all of the following rules:

1. Any two rectangles are either nested (one lies completely inside the other) or disjoint (they do not overlap).
2. Every rectangle has its sides parallel to the x- and y-axes.
3. The sides of any two rectangles are at least $d$ units apart, and this holds even when one rectangle contains the other.
4. For a rectangle $R$, the smallest rectangle that contains it is its super-rectangle. Rectangles that share the same super-rectangle are called co-rectangles, and all co-rectangles under one super-rectangle are placed in a single line: either horizontally (their bottom edges are collinear) or vertically (their left edges are collinear).
5. A rectangle that contains no other rectangle is a photo-rectangle; it is filled with a photo of a fixed size.
6. Exactly one rectangle has no super-rectangle; it is the root rectangle.
7. All corner coordinates are integers.

The sizes and orientations of the photo-rectangles are given and cannot be changed. For every group of co-rectangles you may independently choose whether they are laid out horizontally or vertically. Choose these directions so that the area of the root rectangle is as small as possible, and report that minimum area.

The input contains several test cases. Each test case begins with a line containing two integers $n$ and $d$ ($1 \le n \le 100$, $0 \le d \le 30$), where $n$ is the number of rectangles.

The next $n$ lines describe the rectangles; the $i$-th of these lines describes the rectangle with id $i$. The root rectangle always has id $1$. Let $R_i$ be the set of ids of the rectangles whose super-rectangle is rectangle $i$.

• If $R_i$ is non-empty, the line is k (where k $= |R_i|$) followed by the k ids in $R_i$, all separated by spaces.
• Otherwise rectangle $i$ is a photo-rectangle and its line has the form 0 a b, where $1 \le a \le 30$ and $1 \le b \le 30$ are the lengths of its sides along the x-axis and the y-axis, respectively.

The input ends with a line containing 0 0.

For each test case, print a single line containing the minimum possible area of the root rectangle over all valid choices of horizontal/vertical directions for the co-rectangle groups.

An example configuration that achieves the sample answer: