[ABC374] C - Separated Lunch

C - Separated Lunch

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 300 分

题面

随着KEYENCE总部员工数量的增加，他们决定将总部的部门分成两组，并交错安排他们的午餐时间。

KEYENCE总部有 个部门，第 个部门（）的人数为 。

在将每个部门分配到 A 组或 B 组时，使每组同时用餐，保证 A 组和 B 组的午餐时间不重叠的情况下，找出同时用餐人数的最大可能最小值。 换句话说，找出分配给 A 组的部门的总人数和分配给 B 组的部门的总人数中较大的值的最小可能值。

限制条件

• 所有输入值均为整数。

---

输入

从标准输入中以以下格式输入：

输出

输出同时用餐人数的最大可能最小值。

---

输入样例 1

5
2 3 5 10 12

输出样例 1

17

将部门 1、2 和 5 分配给 A 组，将部门 3 和 4 分配给 B 组，则 A 组有 人，B 组有 人。因此，同时用餐人数的最大可能最小值为 。

无法使两组的人数都少于或等于 16，因此输出为 17。

---

输入样例 2

2
1 1

输出样例 2

1

可能存在多个部门拥有相同人数。

---

输入样例 3

6
22 25 26 45 22 31

输出样例 3

89

例如，将部门 1、4 和 5 分配给 A 组，将部门 2、3 和 6 分配给 B 组，则同时用餐人数的最大可能最小值为 。