题目描述

有一个长度为 $N$ 的未知整数序列 $A$。

给定一个长度为 $N-1$ 的整数序列 $B$。已知对于每个 $i$，都有

请你求出 $A$ 的所有元素之和可能取得的最大值。

输入格式

输入以如下格式从标准输入读入：

$N$ $B_1$ $B_2$ $\ldots$ $B_{N-1}$

输出格式

输出 $A$ 的元素之和可能取得的最大值。

输入输出样例 #1

输入 #1

3
2 5

输出 #1

9

输入输出样例 #2

输入 #2

2
3

输出 #2

6

输入输出样例 #3

输入 #3

6
0 153 10 10 23

输出 #3

53

说明/提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 100$
• $0 \leq B_i \leq 10^5$

样例解释 1

例如，$A$ 可以为 $(2, 1, 5)$，也可以为 $(-1, -2, -3)$，还可以为 $(2, 2, 5)$ 等。在这些方案中，$A$ 的元素之和最大的情况是 $A = (2, 2, 5)$。