#CS1631. 阅读书籍

阅读书籍

题目背景

翻译自 CSES-1631 题。

题目描述

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

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

输入格式

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

第二行有 n 个整数 t1,t2,…,tnt_1,t_2,\dots,t_nt1​,t2​,…,tn​ ，分别代表阅读每本书所需的时间。

输出格式

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

样例

3
2 8 3

16

说明/提示

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

1≤ti≤1091 \leq t_i \le 10^91≤ti​≤109。