Even Partition of Hay Bundles

Farmer John (FJ) has n hay bundles, where the weight of the i-th bundle is \(s_i\). He wishes to distribute all the hay among three farms so that the total weight allocated to each farm is as balanced as possible.

Let \(b_1, b_2, b_3\) denote the total weights assigned to the three farms, with \(b_1 \ge b_2 \ge b_3\). The goal is to minimize \(b_1\), i.e., the maximum weight allocated to any farm. All hay bundles must be assigned to one of the three farms.

Given the weights, calculate the minimum possible value of \(b_1\).

inputFormat

The first line contains an integer \(n\), the number of hay bundles. The second line contains \(n\) space-separated integers \(s_1, s_2, \dots, s_n\), where \(s_i\) is the weight of the i-th hay bundle.

outputFormat

Output a single integer: the minimum possible maximum total weight (\(b_1\)) among the three farms after the allocation.

sample

3
1 1 1

1