在翻修花园时，你决定铺设一条从街道通往正门的碎石路。作为“巨石与鹅卵石社区”的一员，你希望这条路看起来完美无瑕。你已经准备好了一个规则的网格来放置碎石，并且有一个巨大的碎石容器，其中的碎石总量恰好等于网格的总容量。

现在有一个问题：这些碎石还不能完美地填入网格中。每个网格单元都有相同的（固定）容量，且每一块碎石都有一定的重量。你有一个磨石，可以用来将碎石切割成多块，但这样做需要时间，因此你希望通过最少次数的切割，使得碎石能够完美地分布在网格中。

以第一个样例为例，有三个容量为 8 的网格单元，可以按如下方式填充：将重量为 2 和 6 的碎石放入第一个单元。然后将重量为 7 的碎石切割成重量分别为 3 和 4 的两块。接着，另外两个网格单元分别填入重量为 3、5 和 4、4 的碎石。

输入格式

输入包含：

• 一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 100, 1 \le k \le 8$)，分别表示碎石的块数和每个网格单元的容量。
• 一行包含 $n$ 个整数 $w_1, \dots, w_n$ ($1 \le w_i \le 10^6$)，表示每块碎石的重量。

保证 $w_1 + w_2 + \dots + w_n$ 是 $k$ 的倍数。

输出格式

输出将碎石切割成两块的最小次数，使得所有碎石块能够完美填满所有网格单元。

完美铺设在网格中的碎石。CC BY-NC 2.0，作者 markjowen66，来自 Flickr

样例

样例输入 1

5 8
2 4 5 6 7

样例输出 1

1

样例输入 2

2 5
12 13

样例输出 2

4