暂无测试数据。

Cero 国的曾经有一棵古老的有根树，然而这棵树如今已经消失了。历史学家 Creo 希望了解这棵树的原貌，因此查阅了许多古籍文献。据记载，这棵树总共有 $n$ 个节点；同一个节点的不同子节点之间有顺序区分（例如，下图是两种不同的可能情况）；如果一个节点不是根节点且不是其父节点的最后一个子节点，则这个节点是一个“重要节点”。Creo 在还古书上找到了一个神秘的数列 $w_0,w_1,\ldots, w_{n-1}$；对于树上的任意一个不是根节点的节点，如果该节点到根节点的路径上（包括该节点，但不包括根节点）有 $k$ 个“重要节点”，则这个节点的重要程度为 $w_k$；树的重要程度等于树中所有不是根节点的节点的重要程度之和。Creo 想知道，在所有可能情况中，这棵树的重要程度的最大值是多少？

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个正整数 $w_0,w_1,\ldots, w_{n-1}$。

输出格式

一个整数表示答案。

数据规模与约定

对于前 $20\%$ 的数据，$n\le 5$。

对于前 $40\%$ 的数据，$n\le 15$。

对于前 $60\%$ 的数据，$n\le 50$。

对于前 $80\%$ 的数据，$n\le 200$。

对于 $100\%$ 的数据，$1\le n\le 3000$，$1\le a_k< 1000$。

4
1 3 2 4

7