Maximizing Profit in Sais Stones Shipping

A seller has a set of mysterious Sais stones. Each stone has a positive integer weight. Before shipping, the seller can merge any stones arbitrarily to form a new stone whose weight is equal to the sum of the merged stones. However, due to a strong Sais force near the destination, no merging operations are allowed after shipping. All merged stones must be shipped as they are.

There are 10 types of ships available for rent. Each ship has an integer capacity from 1 to 10 (denoted in si units). For a merged stone (or group) with total weight s (1 ≤ s ≤ 10) the seller must rent a ship whose capacity is at least s. The rental cost depends solely on the capacity used. The table below gives the rental cost for each capacity:

After merging, the revenue obtained from selling a stone is given by the square of its weight (i.e. revenue = s² for a merged stone of weight s). However, the cost of renting the ship corresponding to that stone (depending on its total weight) must be subtracted. That is, if a group has total weight s, its profit is:

Profit(s) = s² − (rental fee for capacity s)

The seller has n stones. You are given the weights of these n stones. The seller must group (merge) all stones into several groups such that the sum of weights in each group does not exceed 10 (so that a corresponding ship can be rented). Your task is to determine the maximum total profit the seller can achieve, where the total profit is the sum of the profit values for each group.

Note: The order of merging does not matter. Once the stones are merged and assigned to groups, each group is shipped separately and incurs the rental fee as described. All stones must be used exactly once.

inputFormat

The input consists of two lines:

1. The first line contains an integer n (1 ≤ n ≤ 20), the number of stones.
2. The second line contains n positive integers w₁, w₂, ..., w_n (each between 1 and 10) representing the weights of the stones.

outputFormat

Output a single integer: the maximum total profit achievable by grouping the stones appropriately. The profit of a group with total weight s is defined as s² minus the rental fee for capacity s (according to the table above).

sample

3
3 4 3

45