Problem S
Topside vs Zaun
Jinx and Vi are drafting teams to make the most equitable teams for the fated battle between Topside and Zaun. Currently, there are $N$ people who are undecided on which side they want to fight for. Each person has a skill level $a_i$ that they bring to the table.
While Jinx and Vi would normally want to draft the strongest fighters for their side, they need to drive up ratings for their hit show, Arcane. Instead, they decide to draft teams that are equally matched so they have a few restrictions.
-
Each team must have an equal number of people.
-
Since a person can’t fight for both sides, each person may only be a part of at most one team.
-
The sum of the skill levels of each team must be equal.
-
The size of the team must be as large as possible. If this is not the case, then each fighter can’t get good character development.
They want to figure out the size and skills of the teams that satisfies these condition, or if none exists. Can you help them out?
Input
The first line of input contains $N$ ($1 \leq N \leq 300$), the number of undecided people. The second line of input contains $N$ space-separated integers $a_1, \ldots , a_N$ ($1 \le a_i \le 300$) representing the skill level of each person.
Output
Output one line containing the maximal team size $S$, or $-1$ if a team is impossible to construct.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 1 1 4 1 2 3 |
3 |
