Breaking Bars

Selma is visited by her two grandchildren Elsa and Asle who love chocolate. To be precise, they are especially fond of the brand Nut Cream Puffed Chocolate that comes in bars made up by $6 \times 6$ squares. The bars can be broken along the valleys between squares into smaller rectangular bars of integer dimensions. Due to the fragile nature of this type of chocolate, the bars often break into smaller rectangular bars even before you unpack them (but still only of integer dimensions).

Thus Selma finds herself with a set of rectangular bars of
various dimensions in her candy stash. She knows how important
it is to be fair to children, so not only does she want to give
Elsa and Asle the same amount of chocolate, but also identical
*collections* of rectangular bars (where an $a \times b$ bar is considered
identical to a $b \times
a$ bar). To do this, Selma can break her bars into
smaller pieces. A *break* is the operation of taking an
$a\times b$ bar and
breaking it along a valley to produce two bars of dimensions
$c\times b$ and
$(a-c)\times b$, for some
integer $c\in [1,a-1]$, or
two bars of dimensions $a\times
d$ and $a\times
(b-d)$, for some integer $d\in [1,b-1]$. See Figure 1 for
an example.

Selma would like to give her two grandchildren identical collections of bars, each collection consisting of at least $t$ squares of chocolate. What is the minimum number of breaks she needs to make to be able to do this?

The first line of input contains two integers $n$ and $t$ ($1
\le n \le 50$, $1 \le t
\le 900$), where $n$ is the number of bars Selma has,
and $t$ is the least
number of squares she wants each grandchild to receive. Then
follows a line containing $n$ bar descriptions. A bar
description is on the format “$a$`x`$b$” for
two integers $1 \le a, b \le
6$.

You may assume that the total amount of chocolate squares among the $n$ bars is at least $2t$.

Output the minimum number of breaks needed to obtain two identical collections of bars, each having a total of at least $t$ squares.

Sample Input 1 | Sample Output 1 |
---|---|

4 15 1x2 2x2 3x3 3x5 |
2 |

Sample Input 2 | Sample Output 2 |
---|---|

6 7 1x2 2x3 1x4 3x2 4x1 6x6 |
0 |

Sample Input 3 | Sample Output 3 |
---|---|

5 3 1x1 1x1 1x1 1x1 1x4 |
1 |