和最大

小象拿到了一个序列 $a$，每个数都是整数，现在老师叫他从中选择若干数，使它们的和最大，选的数在这组数中的位置不相邻。小象犯难了，你能帮他吗？

输入格式

第一行两个整数 $n$ 第二行共 $n$个整数$a_1,a_2,…… a_n$ ，表示小象初始得到的序列$a$，空格隔开。

输出格式

一行，输出最大值。

数据范围

• 30% 的数据，$n≤10$；
• 60% 的数据, $n≤10^3$
• 100% 的数据，$n≤10^5$；$0≤a_i≤10^4$

样例数据

输入:

5
2 7 9 3 1

输出:

12