Недавно Джон Доу обнаружил в своем городе «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).
За один день Джон может только один раз поменять один набор на другой. Изначально у него нет никаких предметов. Джон хочет получить набор предметов с как можно большей суммарной стоимостью. Найдите стоимость такого набора и минимальное количество дней, за которое Джон может получить его.
Выходные данные
Выведите через пробел два целых числа: максимально возможную сумму в наборе предметов, который может получить Джон и минимальное количество дней, которое потребуется на то, чтобы получить такой набор.