Диме очень понравился подарок, который он получил от Инны. И еще больше — подарок, который он получил от Сережи.
На радостях Дима решил купить Инне n зайцев. Инна очень обрадовалась, выстроила зайцев в ряд, пронумеровала от единицы до n слева направо и начала кормить морковкой. Инна твердо решила покормить каждого зайца ровно один раз. Но вот в каком порядке их кормить?
Инна заметила, что каждый заяц излучает радость, когда его кормят. Причем радость конкретного зайца зависит от того, покормила ли Инна его соседей перед тем как покормить его. Инна знает, сколько радости излучит заяц, если на момент, когда Инна его кормит не покормлены соседние зайцы, покормлен один из соседних зайцев или покормлены оба. Обратите внимание, что у зайцев с номерами 1 и n нет левого и правого соседа соответственно, то есть у них никогда не могут быть покормлены оба соседа.
Помогите Инне максимизировать суммарную радость, которую излучат зайцы. :)