CF364B.Free Market

John Doe has recently found a "Free Market" in his city — that is the place where you can exchange some of your possessions for other things for free.

John knows that his city has n items in total (each item is unique). You can bring any number of items to the market and exchange them for any other one. Note that each item is one of a kind and that means that you cannot exchange set {a, b} for set {v, a}. However, you can always exchange set x for any set y, unless there is item p, such that p occurs in x and p occurs in y.

For each item, John knows its value c__i. John's sense of justice doesn't let him exchange a set of items x for a set of items y, if s(x) + d < s(y) (s(x) is the total price of items in the set x).

During one day John can exchange only one set of items for something else. Initially, he has no items. John wants to get a set of items with the maximum total price. Find the cost of such set and the minimum number of days John can get it in.

约翰·多伊尔最近在自己的城市发现了一个“自由市场”——在这里，你可以免费用自己的物品交换其他物品。

约翰知道，他的城市总共有 $n$ 种物品（每种物品都是独一无二的）。你可以携带任意数量的物品前往市场，并用它们交换任意一种其他物品。注意，每种物品都是唯一的，这意味着你不能用集合 $\{a,\,b\}$ 去交换集合 $\{v,\,a\}$。然而，只要集合 $x$ 与集合 $y$ 没有公共元素（即不存在某个物品 $p$ 同时属于 $x$ 和 $y$），你总是可以将集合 $x$ 交换为集合 $y$。

对于每种物品 $i$，约翰知道其价值 $c_i$。约翰的正义感使他拒绝进行如下交换：用物品集合 $x$ 交换物品集合 $y$，当且仅当 $s(x) + d < s(y)$ 成立（其中 $s(x)$ 表示集合 $x$ 中所有物品价值的总和）。

约翰每天最多只能进行一次交换（即用一个物品集合交换另一个物品集合）。初始时，他不持有任何物品。约翰希望获得一个总价值最大的物品集合。请找出该集合的总价值，以及约翰获得该集合所需的最少天数。

The first line contains two space-separated integers n, d (1 ≤ n ≤ 50, 1 ≤ d ≤ 104) — the number of items on the market and John's sense of justice value, correspondingly. The second line contains n space-separated integers c__i (1 ≤ c__i ≤ 104).

第一行包含两个以空格分隔的整数 $n$、$d$（$1 ≤ n ≤ 50$，$1 ≤ d ≤ 10^4$）——分别表示市场上物品的数量和约翰的正义感数值。
第二行包含 $n$ 个以空格分隔的整数 $c_i$（$1 ≤ c_i ≤ 10^4$）。

Print two space-separated integers: the maximum possible price in the set of items John can get and the minimum number of days needed to get such set.

输出两个用空格分隔的整数：John 能获得的物品集合中的最高可能价格，以及获得该集合所需的最少天数。

In the first sample John can act like this:

• Take the first item (1 - 0 ≤ 2).
• Exchange the first item for the second one (3 - 1 ≤ 2).
• Take the first item (1 - 0 ≤ 2).

在第一个样例中，John 可以这样操作：

• 拿取第一件物品（$1 - 0 \leq 2$）。
• 将第一件物品换成第二件物品（$3 - 1 \leq 2$）。
• 拿取第一件物品（$1 - 0 \leq 2$）。