Equal Cost Packages

The first line of input contains an integer 'N', the number of items.

The second line contains 'N' space-separated integers, representing the itemCosts array.

Print a single integer representing the maximum number of packages that can be formed.

The main challenge is that the target cost for the packages is not given. You must determine the optimal target cost yourself.

The target cost for a package must be a sum that can be formed by either one or two items from the list.

Sample Input 1:

6
10 20 30 40 50 60

Sample Output 1:

3

Explanation for Sample 1:

Let's try a target cost of 70.
  We can form the pair `(10, 60)`. Remaining items: `{20, 30, 40, 50}`.
  We can form the pair `(20, 50)`. Remaining items: `{30, 40}`.
  We can form the pair `(30, 40)`. No items left.
With a target cost of 70, we can form 3 packages. This is the maximum possible.

Sample Input 2:

3
6 6 6

Sample Output 2:

3

Explanation for Sample 2:

If we try a target cost of 12, we can form one pair `(6, 6)`.   One item `6` is left over. We can't form another package of cost 12. Total packages: 1.
If we try a target cost of 6, we can form three single-item packages: `(6)`, `(6)`, `(6)`.
The maximum number of packages is 3.

Expected Time Complexity:

The expected time complexity is roughly O(S * N), where S is the number of unique possible sums and N is the number of items.

Constraints:

1 <= N <= 100
1 <= itemCosts[i] <= 1000

Time limit: 1 sec