Костя — профессиональный киберспортсмен, специализирующийся на дисциплине Dota 2. Недавно компания Valve, разработчик этой игры, выпустила новый патч, перевернувший баланс игры с ног на голову. Костя, являясь капитаном команды, понимает, что наибольшая ответственность лежит на нем, поэтому он хочет прибегнуть к анализу нововведений патча с математической точки зрения, чтобы выбирать наилучших героев для своей команды в каждом матче.
В матче Dota 2 участвуют две команды, каждая из которых должна взять для себя некоторых героев, за которых впоследствии будут играть члены этой команды, причем запрещено выбирать одного и того же героя несколько раз, даже разными командами. На крупных киберспортивных турнирах, таких, в которых собирается участвовать команда Кости, матчи проходят в режиме Captains Mode. В этом режиме для выбора героев капитаны команд в определенном, заранее установленном порядке совершают одно из двух возможных действий: пик (pick) или бан (ban).
- Пик — это выбор героя для своей команды. После того, как капитан команды сделал пик, герой, которого он выбрал, отправляется в его команду (за него впоследствии будет играть один из членов команды) и больше не может быть выбран ни одной из команд.
- Бан — это запрет героя. После бана герой не отправляется ни в одну из команд, однако он также больше не может быть выбран ни одной из команд.
Капитан команды может пропустить пик или бан. В случае пропуска пика в его команду добавляется случайный герой из тех, что были доступны на данный момент, а в случае пропуска бана не запрещается ни один герой, как будто этого бана и не было.
Костя уже определил силу всех героев с учетом исправлений нового патча. Разумеется, Костя знает и порядок пиков и банов. Сила команды равна сумме сил входящих в нее героев, и обе команды, участвующие в матче, стремятся максимизировать разницу в силе в свою сторону. Помогите Косте определить, у какой команды в матче — у первой или у второй — преимущество, и насколько оно велико.