Enigma 1491: Tile trials

I've recently found myself with more time on my hands, so I renewed my subscription to New Scientist and have been using the weekly Enigma puzzles to provide me with a weekly pragmatic programming exercise.

Normally these are amenable to short Perl program to analyse the problem space to come up with the solution in a few seconds. However this week's was a bit trickier:

Tile trials

DICK has a box of rectangular tiles. Each is a different size, the dimensions being 1 × 3, 2 × 4, 3 × 5, 4 × 6 and so on.

He takes some tiles out of the box, first the 1 × 3, then the 2 × 4, then the 3 × 5, and so on, with the aim of fitting together all those that he has taken into a rectangle that has no gaps and no overlaps.

Assuming he takes more than one tile out of the box, how many tiles must he take out to create (a) the smallest possible rectangle, and (b) the next smallest possible rectangle?

New Scientist Enigma 1491, Richard England

The Perl program I wrote ran and found the first solution in a few seconds, but took 50m26s to find both the necessary solutions. So while it was running I wrote an equivalent program in C. It's been a few years since I did any serious C coding, but once I remembered what the equivalent C constructs to Perl's next and last were (continue and break), I got it compiled and it ran and found the solutions in 11.3s.