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

题目描述

小 $W$ 过生日，小 $Z$、$X$、$Y$ 都来庆祝（蹭饭）。小 $W$ 有一块巨大的生日蛋糕，蛋糕共有 $N$ 块，排成一排。小 $W$ 每次切一块，然后分给某个人。每块蛋糕都有糖霜 $a_i$ 克。切蛋糕时，只能从蛋糕剩下的两端中选择一端，然后切掉一块。第 $k$ 次切下来的蛋糕，若 $k \mod 4=1$ 则小 $W$ 能得到 $a_i$ 克糖霜，否则得到 $\lfloor \frac{a_i}{4} \rfloor$ 克糖霜。刷小聪明（老奸巨滑）的小 $W$ 想要得到最多的糖霜，请你帮帮可爱的她。

输入格式

第一行一个正整数 $N$。

接下来一行 $N$ 个整数，表示序列 $a$。

输入格式

一个整数，表示小 $W$ 最多能获得的糖霜。

样例 #1

样例输入 #1

5
1 9 4 8 4

样例输出 #1

16

提示

$1 \leq 10^3 \leq n$

$1 \leq a_i \leq 10^6$