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

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

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

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