### Problem Statement

A prefix-free code of size N which uses K characters is a set of N distinct strings such that
• each string of the set contains only characters '0','1', ..., ('0'+K-1)
• no string of the set is a prefix of any other string of the set.
The cost of a prefix-free code can be calculated as sum of costs of characters used to write down all strings of the set.

You are given the size of the code N and the costs of using the characters characterCosts. Return the minimal possible cost of a prefix-free code of size N which uses these character costs.

### Definition

 Class: PrefixFreeCode Method: minCost Parameters: int, int[] Returns: int Method signature: int minCost(int N, int[] characterCosts) (be sure your method is public)

### Constraints

-N will be between 2 and 500, inclusive.
-characterCosts will contain between 2 and 50 elements, inclusive.
-Each element of characterCosts will be between 1 and 100, inclusive.

### Examples

0)

 `3` `{1,4}`
`Returns: 11`
 The cheapest code of size 3 is {"00","01","1"}.
1)

 `3` `{1,3,5}`
`Returns: 9`
 Here exist two cheapest codes - {"0","1","2"} and {"00","01","1"}.
2)

 `500` ```{ 2, 4, 6, 8,10,12,14,16,18,20, 22,24,26,28,30,32,34,36,38,40, 42,44,46,48,50,52,54,56,58,60, 62,64,66,68,70,72,74,76,78,80, 82,84,86,88,90,92,94,96,98,100}```
`Returns: 9464`
3)

 `500` `{1,2,3,4,5,6,7,8,9,10}`
`Returns: 4732`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10419

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13952&pm=10419

Nickolas

#### Testers:

Rustyoldman , timmac , it4.kp , StevieT , vexorian

#### Problem categories:

Greedy, Simulation