Selma 的两个孙子 Elsa 和 Asle 来家里做客，他们非常喜欢吃巧克力。确切地说，他们特别喜欢 Nut Cream Puffed Chocolate 这个品牌，这种巧克力由 $6 \times 6$ 的方块组成。巧克力棒可以沿着方块之间的凹槽掰成更小的矩形块，且尺寸均为整数。由于这种巧克力非常易碎，它们在拆开包装之前往往就已经碎成了更小的矩形块（但尺寸仍然是整数）。

因此，Selma 在她的糖果储藏室里发现了一堆各种尺寸的矩形巧克力棒。她深知公平对待孩子的重要性，所以她不仅想给 Elsa 和 Asle 同样多的巧克力，还想给他们完全相同的矩形巧克力棒集合（其中 $a \times b$ 的巧克力棒被视为与 $b \times a$ 的巧克力棒相同）。为了做到这一点，Selma 可以将她现有的巧克力棒掰成更小的块。一次“掰”的操作是指将一块 $a \times b$ 的巧克力棒沿着凹槽掰开，产生两块尺寸分别为 $c \times b$ 和 $(a - c) \times b$ 的巧克力棒（其中 $c \in [1, a - 1]$ 为整数），或者产生两块尺寸分别为 $a \times d$ 和 $a \times (b - d)$ 的巧克力棒（其中 $d \in [1, b - 1]$ 为整数）。参见图 B.1 中的示例。

Selma 希望给她的两个孙子提供完全相同的巧克力棒集合，每个集合包含至少 $t$ 个巧克力方块。请问她最少需要掰多少次才能做到这一点？

图 B.1：样例输入 1 的解释。首先对 $3 \times 5$ 的巧克力棒（橙色）进行一次纵向掰开，然后在新建的 $3 \times 2$ 的巧克力棒（蓝色）上进行一次横向掰开。这样 Elsa 和 Asle 每人都可以得到一块 $1 \times 2$、一块 $2 \times 2$ 和一块 $3 \times 3$ 的巧克力棒，总共各 15 个方块。

输入格式

输入的第一行包含两个整数 $n$ 和 $t$ ($1 \le n \le 50, 1 \le t \le 900$)，其中 $n$ 是 Selma 拥有的巧克力棒数量，$t$ 是她希望每个孙子收到的最少方块数。接下来的一行包含 $n$ 个巧克力棒的描述。巧克力棒的描述格式为 “axb”，其中 $a, b$ 为 $1 \le a, b \le 6$ 的整数。

你可以假设这 $n$ 块巧克力棒包含的巧克力方块总数至少为 $2t$。

输出格式

输出为了获得两个相同的巧克力棒集合（每个集合总方块数至少为 $t$）所需的最少掰开次数。

样例

样例输入 1

4 15
1x2 2x2 3x3 3x5

样例输出 1

2

样例输入 2

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

样例输出 2

0

样例输入 3

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

样例输出 3

1