Карточки пронумерованы числами 1, 2, 3,…, N. На каждой из них написано какое-либо целое неотрицательное число. Миша просматривает карточки в порядке возрастания номеров. Какие-то из них он будет выбирать, а остальные – пропускать, причем после «пропущенной» карточки обязательно должна следовать «выбранная» карточка. Числа, записанные на «выбранных» карточках, Миша суммирует по следующему правилу:
число на очередной «выбранной» карточке добавляется к накопленной сумме, если предыдущая карточка тоже была «выбранной»;
число на очередной «выбранной» карточке удваивается, а затем добавляется к накопленной сумме, если предыдущая карточка была «пропущенной».
Начальная сумма равна числу, записанному на первой карточке, если она была выбрана, либо считается нулевой, если первая карточка была пропущена. Интересно, какую максимальную накопленную сумму может получить Миша, выбирая карточки по своему усмотрению и суммируя числа с «выбранных» карточек по указанному правилу?