暂无测试数据。

题目描述

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。

给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

输入格式

第一行，包含两个正整数 $n$，代表请求的数量。

接下来的一行，包含 $n$ 个正整数，代表每个服务花费的时间。

输出格式

一行一个整数，表示总预约时间最长的数值。

样例 #1

样例输入 #1

4
1 2 3 1

样例输出 #1

4

样例 #2

样例输入 #2

8
2 1 4 5 3 1 1 3

样例输出 #2

12