B. Free Market
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Недавно Джон Доу обнаружил в своем городе «Free Market» — место, где можно бесплатно обменять свои вещи на другие.

Джон знает, что всего в его городе есть n предметов (каждый существует в единственном экземпляре). На рынок можно принести любой набор предметов и обменять его на любой другой. Заметьте, что предметы существуют в единственном экземпляре и это значит, что нельзя поменять набор {a, b} на набор {v, a}. Но при этом всегда можно обменять набор x на любой набор y, если не существует предмета p, такого, что p входит в x и p входит в y.

Для каждого предмета Джон знает его стоимость ci. Совесть не позволяет Джону обменять набор предметов x на набор предметов y, если s(x) + d < s(y) (s(x) — суммарная стоимость предметов в наборе x).

За один день Джон может только один раз поменять один набор на другой. Изначально у него нет никаких предметов. Джон хочет получить набор предметов с как можно большей суммарной стоимостью. Найдите стоимость такого набора и минимальное количество дней, за которое Джон может получить его.

Входные данные

В первой строке записаны через пробел два целых числа n, d (1 ≤ n ≤ 50, 1 ≤ d ≤ 104) — количество предметов на рынке и показатель совести Джона, соответственно. Во второй строке через пробел записано n целых чисел ci (1 ≤ ci ≤ 104).

Выходные данные

Выведите через пробел два целых числа: максимально возможную сумму в наборе предметов, который может получить Джон и минимальное количество дней, которое потребуется на то, чтобы получить такой набор.

Примеры
Входные данные
3 2
1 3 10
Выходные данные
4 3
Входные данные
3 5
1 2 3
Выходные данные
6 2
Входные данные
10 10000
10000 9999 1 10000 10000 10000 1 2 3 4
Выходные данные
50010 6
Примечание

В первом примере Джон может действовать следующим образом:

  • Взять первый предмет (1 - 0 ≤ 2).
  • Обменять первый предмет на второй (3 - 1 ≤ 2).
  • Взять первый предмет (1 - 0 ≤ 2).