Ограбление домов
Вы планируете совершить ограбление на одной улице. На ней находится
n домов, и вы знаете, какую сумму денег можно получить в каждом из них. Сигнализация автоматически вызыва́ет полицию, если в одну ночь будут ограблены два соседних дома.Какую максимальную сумму можно взять за один раз, не рискуя быть пойманным?
Ввод
В первой строке входных данных задаётся одно целое число
n (1 ≤ n ≤ ).В следующей строке перечислены
n целых чисел (1 ≤ ≤ ), указывающих, сколько денег можно получить из каждого дома.Вывод
Программа должна вывести максимально возможную сумму, которую можно взять, не будучи пойманным.
Примеры
Ввод | Вывод |
4
1 2 5 1 | 6 |
5
3 17 12 3 7 | 24 |
Объяснение
- 1 + 5
- 17 + 7 (пропуская некоторые дома между ними)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB