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

题目描述

小 \(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\)