В связи с увеличением количества студентов в Берляндском государственном университете было решено оборудовать новый компьютерный кабинет. Вам было поручено купить мыши, и как можно дешевле, ведь в стране кризис!
Компьютеры, заказанные для кабинета, оказались существенно разными. Некоторые из них имеют только порты USB, некоторые — только PS/2, а на некоторых присутствуют оба варианта.
На сайте компьютерного магазина вы нашли прайс-лист, в котором для m мышей указаны цена и тип порта, к которому мышь можно подключить (USB или PS/2). Каждая мышь из списка есть в магазине в единственном экземпляре.
Вы хотите купить некоторый набор мышей из данного прайс-листа так, чтобы в первую очередь максимизировать количество оборудованных мышами компьютеров (не гарантируется, что удастся оборудовать все компьютеры), а при равенстве этой величины минимизировать суммарную стоимость купленных мышей.
Выходные данные
Выведите два целых числа через пробел — количество оборудованных компьютеров и суммарную стоимость приобретённых мышей.
Примечание
В первом примере можно купить первые три мыши, оборудовав один из компьютеров с USB входом мышью с USB выходом, а две PS/2 мыши подключить к компьютеру с PS/2 и компьютеру с обоими входами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1 1
4
5 USB
6 PS/2
3 PS/2
7 PS/2
|
3 14
|