题目描述

一排 N 个平台，编号 1 到 N。每个平台 i 上有一个分数 s[i]（可正可负）。

你从平台 1 出发，目标是到达平台 N。在平台 i 上，你可以跳跃到平台 i+1、i+2 或 i+3（不能超出 N）。到达某个平台时，你会获得该平台的分数（负数则扣分）。

求从平台 1 到平台 N 能获得的最大总分。起点和终点的分数都会计入。

输入格式

第一行一个整数 N 第二行 N 个整数 s[1], s[2], ..., s[N]

输出格式

一个整数：最大总分

3
5 -10 3

8

5
1 2 3 4 5

15

数据范围与提示

1 ≤ N ≤ 10000 -1000 ≤ s[i] ≤ 1000