«Своя игра» — интеллектуальная игра, в которой игроки отвечают на вопросы и зарабатывают очки. Компания Q проводит турнир по упрощенной версии «Своей игры» среди лучших IT компаний. По счастливой случайности в финал турнира пробились давние конкуренты: компания R1 и компания R2.

В финале будет разыграно n вопросов, из которых m вопросов-аукционов и n - m обычных вопросов. Каждый вопрос имеет цену. Цена i-го вопроса составляет a_i очков. В процессе игры игроки выбирают вопросы, при этом, если вопрос является аукционом, то его цена может быть изменена выбравшим вопрос игроком, если его текущее количество очков строго больше цены вопроса. Новая цена вопроса не может быть меньше исходной цены вопроса и не может быть больше текущего количества очков игрока, который выбрал вопрос. Правильный ответ на вопрос приносит игроку количество очков, равное цене вопроса. Неправильный ответ на вопрос уменьшает количество очков игрока на значение цены вопроса.

Игра будет проходить следующим образом. Сначала компания R2 выбирает вопрос, далее выбирает вопрос тот, кто первым правильно ответил на последний вопрос. Если никто не ответил на вопрос, право выбора вопроса остается у последнего выбирающего.

Все сотрудники компании R2 болеют за свою команду. Они хотят посчитать, какое максимально возможное количество очков сможет получить команда R2, если удача будет на их стороне всю игру (будут всегда первыми правильно отвечать на вопросы). Наверное, вы не будете сильно удивлены, но эту задачу опять поручили решить вам.