CF364B Free Market

John Doe 最近在他所在的城市发现了一个“自由市场”——在那里，你可以免费用自己的某些物品交换其他物品。 John 知道他所在的城市一共有 $n$ 件物品（每件物品都是独一无二的）。你可以带任意数量的物品去市场，并将它们交换成其他任意的物品。注意，每件物品都是唯一的，这意味着你不能把集合 ${a,b}$ 换成集合 ${v,a}$。但是，除非存在物品 $p$ 同时出现在 $x$ 和 $y$ 中，你总是可以将集合 $x$ 换成集合 $y$。 对于每件物品，John 都知道其价值 $c_{i}$。John 的正义感不允许他用物品集合 $x$ 换取物品集合 $y$，如果 $s(x) + d < s(y)$（$s(x)$ 表示集合 $x$ 中所有物品的总价值）。 一天之内，John 只能进行一次用物品集合进行的交换操作。起初，他没有任何物品。John 想要获得一组总价值最大的物品。请你求出，他能获得的物品集合的最大总价值是多少，以及最少需要多少天才能得到这一集合。

第一行包含两个用空格分隔的整数 $n$、$d$（$1 \leq n \leq 50$，$1 \leq d \leq 10^{4}$）——代表市场上物品的数量以及 John 的正义感值。第二行包含 $n$ 个用空格分隔的整数 $c_{i}$（$1 \leq c_{i} \leq 10^{4}$）。

输出两个用空格分隔的整数：John 能够获得的物品集合的最大总价值，以及获得这一集合所需的最少天数。

在第一个样例中，John 可以这样操作： - 取第一个物品（$1-0 \leq 2$）。 - 用第一个物品交换第二个物品（$3-1 \leq 2$）。 - 取第一个物品（$1-0 \leq 2$）。 由 ChatGPT 5 翻译