Farmer John vừa nhận một chuyến hàng mới gồm \(N\) kiện cỏ khô (\(1 \le N \le 20\)), trong đó kiện thứ \(i\) có kích thước \(S_i\) (\(1 \le S_i \le 100\)). Ông muốn chia các kiện cỏ vào ba kho sao cho công bằng nhất có thể.

Sau khi suy nghĩ kỹ, FJ quyết định rằng một cách chia các kiện cỏ “công bằng” phải làm cho phần lớn nhất nhỏ nhất có thể. Cụ thể, gọi \(B_1\), \(B_2\) và \(B_3\) lần lượt là tổng kích thước của tất cả các kiện được đặt vào kho 1, 2 và 3 (với \(B_1 \ge B_2 \ge B_3\)), FJ muốn làm cho \(B_1\) nhỏ nhất có thể.

Ví dụ, nếu có 8 kiện với các kích thước:

2 4 5 8 9 14 15 20

Một cách chia công bằng là:

Kho 1: 2 9 15   B_1 = 26
Kho 2: 4 8 14   B_2 = 26
Kho 3: 5 20     B_3 = 25

Hãy giúp FJ xác định giá trị của \(B_1\) trong một cách chia các kiện cỏ công bằng.

Dữ liệu vào

• Dòng 1 chứa số kiện cỏ \(N\).
• Các dòng từ 2 đến \(1+N\): dòng \(i+1\) chứa \(S_i\), kích thước của kiện thứ \(i\).

Dữ liệu ra

In ra giá trị của \(B_1\) trong một cách chia các kiện cỏ công bằng.

Ví dụ

8
14
2
5
15
8
9
20
4

26

Nguồn

USACO 2012 January Contest, Silver - Bale Share: https://usaco.org/index.php?page=viewproblem2&cpid=107

Tác giả: Fatih Gelgi, 2010.