Fill the Tray With Every Piece

A chocolatier has a rectangular tray width cells wide and height cells tall, and a set of rectangular slabs pieces, where [w, h] is a slab w cells wide and h cells tall. A slab may be turned by 90 degrees (becoming h wide and w tall), but it must lie along the grid lines.

Return True if all the slabs can be placed in the tray so that they do not overlap and every cell of the tray is covered, and False otherwise.

Examples

Input:  width = 3, height = 2, pieces = [[1, 2], [2, 2]]
Output: True

Input:  width = 3, height = 3, pieces = [[2, 2], [1, 5]]
Output: False
Explanation: the areas add up to 9, but the 1 x 5 slab does not fit in a 3 x 3 tray.

Input:  width = 4, height = 4, pieces = [[1, 3], [1, 3], [1, 3], [1, 3], [2, 2]]
Output: True
Explanation: the 2 x 2 slab sits in the middle and the four 1 x 3 slabs circle it like a pinwheel.

Constraints

• 1 <= width, height <= 40
• 1 <= len(pieces) <= 25, and 1 <= w, h <= 40 for every piece

Goals

• Always fill the first empty cell so each packing is built in only one order
• Treat identical pieces as one kind with a count so they are never swapped with each other