题目描述

有 $n$ 本书，Kotivalo 和 Justiina 打算把它们全部读完。对于每本书，你们都知道阅读所需的时间。

他们都要从头到尾读完每本书，而且不能同时读一本书。请问，完成所有书籍阅读所需的最短总时间是多少？

输入格式

第一行输入整数 $n$，代表书籍数量。

第二行有 $n$ 个整数 $t_1, t_2, \ldots, t_n$，分别代表阅读每本书所需的时间。

输出格式

输出一个整数，表示完成所有书籍阅读所需的最短总时间。

样例

3
2 8 3

16

数据范围

• $1 \le n \le 2 \times 10^5$
• $1 \le t_i \le 10^9$