Может stgatilov знает))

Задача 5: Разновкусные конфеты.

Ключевая идея в том, чтобы покрасить все типы конфет в A цветов случайным образом. Теперь, если мы наберём конфеты A различных цветов, то конечно же мы и A различных типов конфет наберём. Ну, запустим динамику по подмаскам: состояние dp[i][mask] — в какую стоимость можно набрать конфеты с цветами из mask, используя первые i пачек конфет. Переходы сообразить нетрудно.

Возникает проблема: наше решение может быть неоптимальным. Ну, представим себе A конфет из оптимального решения. Мы это решение нашли, только если все эти конфеты покрасились в A различных цветов. А это и происходит с вероятностью $$$\frac{A!}{A^A}$$$. Это немаленькая вероятность. Можно позапускать наше решение много раз, пока вероятность того, что мы ни разу не покрасили конфеты из оптимального решения в A различных цветов, не станет близко к нулю.

Альтернативное решение без случайности тоже укладывалось во временные ограничения. Можно перебрать одну пачку, две, три или четыре простыми вложенными циклами. Также можно жадно брать пачки от самой дешёвой к самой дорогой, пока не наберём A конфет. И можно даже больше: перебрать одну, две или три пачки вложенными циклами, а остаток добрать жадно. Если хорошенько проработать случаи, то можно показать, что работает решение, которое делает эти переборы в нужном порядке и отсекает большие пачки по пути (например, перебрав все пары пачек, можно выкинуть все пачки размера A-1 и больше, потому что к пачке X размера A-1 не понадобится докупать больше одной другой пачки, а значит все оптимальные решения, использующие пачку X мы уже нашли).