History of OI -> V OI 1997/1998 -> Problems

 News About Olympic History of OI XVII OI 2009/2010 XVI OI 2008/2009 XV OI 2007/2008 XIV OI 2006/2007 XIII OI 2005/2006 XII OI 2004/2005 XI OI 2003/2004 X OI 2002/2003 IX OI 2001/2002 VIII OI 2000/2001 VII OI 1999/2000 VI OI 1998/1999 V OI 1997/1998 Stage III - results Stage II - results Stage I - results Problems Regulations Schedule Stats IV OI 1996/1997 III OI 1995/1996 II OI 1994/1995 I OI 1993/1994 OI books National team Olympic camps Photo gallery Links SIO MAIN
Niebieskie ksi.eczki

The lightest language

 III stage contest

Alphabet Ak consists of k initial letters of English alphabet. A positive integer called a weight is assigned to each letter of the alphabet. A weight of a word built from the letters of the alphabet Ak is the sum of weights of all letters in this word. A language over an alphabet Ak is any finite set of words built from the letters of this alphabet. A weight of a language is the sum of weights of all its words. We say that the language is prefixless if for each pair of different words w, v from this language w is not a prefix of v.

We want to find out what is the minimal possible weight of an n-element, prefixless language over an alphabet Ak.

#### Example

Assume that k = 2 , the weight of the letter a - W(a)=2 and the weight of the letter b - W(b) = 5. The weight of the word ab - W(ab)= 2+5=7. W(aba)=2+5+2=9. The weight of the language J = {ab, aba, b} - W(J) = 21. The language J is not prefixless, since the word ab is a prefix of aba. The lightest tree-element, prefixless language over the alphabet A2 (assuming that weights of the letters are as before) is {b, aa, ab}; its weight is 16.

Write a program that:

• reads two integers n, k and the weights of k letters of an alphabet Ak from the text file NAJ.IN;
• computes the minimal weight of a prefixless, n-element language over the alphabet Ak;
• writes the result to the text file NAJ.OUT.

#### Input

In the first line of the input file NAJ.IN there are two positive integers n and k separated by a single space, (2<=n<=10000, 2<=k<=26). These are the number of words in a language and the number of letters in an alphabet respectively. The second line contains k positive integers separated by single spaces. Each of them is not greater than 10000. The i-th number is the weight of the i-th letter.

#### Output

In the first and only line of the output file NAJ.OUT there should be written one integer - the weight of the lightest prefixless n-element language over the alphabet Ak.

#### Example

For the input file NAJ.IN:

```3 2
2 5
```

the correct result is the output file NAJ.OUT:
`16`

Print friendly version