John Doe 最近在他的城市发现了一个“自由市场”——在那里你可以用你的一些财产免费交换其他东西。
约翰知道他的城市总共有 n 个项目(每个项目都是唯一的)。您可以将任意数量的物品带到市场并将其兑换成任何其他物品。请注意,每个项目都是独一无二的,这意味着您不能将集合 {a, b} 交换为集合 {v, a}。但是,您始终可以将集合 x 交换为任何集合 y,除非存在项 p,使得 p 出现在 x 中并且 p 出现在 y 中。
对于每一项,John 都知道它的值 ci。约翰的正义感不允许他用一组物品 x 交换一组物品 y,如果 s(x) + d < s(y)(s(x) 是集合 x 中物品的总价格)。
在一天中,约翰只能用一套物品交换其他物品。最初,他没有任何物品。约翰想要获得总价最高的一组物品。求出该套装的成本以及约翰可以拿到它的最少天数。
输入
第一行包含两个空格分隔的整数 n, d (1 ≤ n ≤ 50, 1 ≤ d ≤ 104) — 相应地,市场上的物品数量和约翰的正义感值。第二行包含 n 个空格分隔的整数 ci (1 ≤ ci ≤ 104)。
输出
打印两个以空格分隔的整数:John 可以获得的这组物品中的最大可能价格以及获得该组物品所需的最短天数。
示例
输入 #1
3 2 1 3 10
输出 #1
4 3
输入 #2
3 5 1 2 3
输出 #2
6 2
输入 #3
10 10000 10000 9999 1 10000 10000 10000 1 2 3 4
输出 #3
50010 6
注意
在第一个示例中,John 可以这样做:
- 取第一项 (1 - 0 ≤ 2)。
- 将第一项替换为第二项 (3 - 1 ≤ 2)。
- 取第一项 (1 - 0 ≤ 2)。