You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1631 题。

题目描述

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

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

输入格式

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

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

输出格式

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

样例

3
2 8 3

16

说明/提示

$1 \le n \le 2\cdot 10^5$；

$1 \leq t_i \le 10^9$。