Reconstructing Sticks

George once had several sticks of the same length. One day, he randomly cut these sticks into smaller segments, with the condition that no segment is longer than \(50\). Now, he wants to reconstruct the original sticks but has forgotten both the number of sticks and their original length.

Given the lengths of the segments, determine the minimum possible original stick length that could have produced these pieces when cut.

The original stick length must be at least the length of the longest segment and must exactly divide the total length of all segments.

Formally, let \(S\) be the sum of all segment lengths and \(m\) be the maximum segment length. You are to find the smallest integer \(L\) (with \(L \ge m\)) such that \(L\) divides \(S\) and the segments can be partitioned into groups each summing exactly to \(L\).

Note: The pieces can be arranged in any order when forming a stick. Each segment must be used exactly once.

inputFormat

The first line of input contains a single integer \(N\), representing the number of segments.

The second line contains \(N\) space-separated positive integers, each indicating the length of a segment.

outputFormat

Output a single integer, the minimum possible original stick length that can be formed using all the segments.

sample

9
5 2 1 5 2 1 5 2 1

6