Orpheus found a way to send messages to Eurydice at long last using his songs as messages. But Orpheus could only send messages through two different signals, called dots and dashes. There are a total of \(\mathbf{N}\) kinds of symbols in Orpheus's song. He decided to send his messages by changing every symbol in his songs to combinations of dots and dashes. These combinations will be referred to as codes. And there were limitations he had to follow if he wanted to succeed:

• No code will be the prefix of another code. In other words, when encoding a symbol none of the codes should be the beginning of another code.
• No code will use more than \(\mathbf{K}\) dashes and dots. So if \(\mathbf{K}\) is 2 the code of a symbol could be one of these:..,--,.-,-.,.,-

After the codes are decided every symbol in your song will be translated into its code. To maximize your chance for your message to reach Eurydice choose the representation code of every symbol in the way that minimizes the total number of dots and dashes that your translated song will contain.

If the song cannot be translated, print \(-1\) instead.

Input

• The first line contains \(2\) integers:
  • \(2\leq\mathbf{N}\leq10^5\) (The number of symbol types)
  • \(2\leq\mathbf{K}\leq10^2\) (The maximum length for a symbol's representation)
• The second line contains \(\mathbf{N}\) integers:
  • \(1\leq\mathbf{a_i}\leq10^9\) (Number of times that symbol is used)

Output

Print \(1\) positive integer, the minimum length of the translated song, if it can be translated.

Print \(-1\) if not.

Example

Input 1:

10 5
2 3 4 4 5 8 16 16 21 35

Output 1:

325

Input 2:

10 4
2 3 4 4 5 8 16 16 21 35

Output 2:

333

Input 3:

10 3
2 3 4 4 5 8 16 16 21 35

Output 3:

-1

Explanation

Input 1: The codes of the symbols could be:

• ..... for the 1st symbol that was used 2 times.
• ....- for the 2nd symbol that was used 3 times.
• ..-.. for the 3rd symbol that was used 4 times.
• ..-.- for the 4th symbol that was used 4 times.
• ...- for the 5th symbol that was used 5 times.
• ..-- for the 6th symbol that was used 8 times.
• -.. for the 7th symbol that was used 16 times.
• -.- for the 8th symbol that was used 16 times.
• .- for the 9th symbol that was used 21 times.
• -- for the 10th symbol that was used 35 times.

Which sums up to: \(5\cdot2+5\cdot3+5\cdot4+5\cdot4+4\cdot5+4\cdot8+3\cdot16+3\cdot16+2\cdot21+2\cdot35=325\)