该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

设有 $N$ 个正整数$（1≤N≤10^3）$，其中每一个数$a_i$均是整数$(1\le a_i \le 10^4)$。

从这$N$ 个数中任取出若干个数（不能取相邻的数），要求得到一种取法，使取到的数之和为最大。

例如：当$N=5$时，有 $5$个数分别为：$13,18,28,45,21$；

此时，有许多种取法，如：$13,28,21$ 和为 $62$；

$13,45$ 和为 $58$；$18,45$ 和为 $63$；…

输入

第一行是一个整数$N$；

第二行有 $N$ 个符合条件的整数。

输出

一个整数，即最大和。

样例

输入

5
13 18 28 45 21

输出

63