#P18805. [POI1998] 最轻的前缀语言

[POI1998] 最轻的前缀语言

[POI1998] 最轻的前缀语言

题目描述

有一个由前 kk 个小写英文字母组成的字母表,每个字母都有一个正整数权值。一个字符串的权值是其中所有字母权值的总和。

一个语言是一个由不同字符串组成的有限集合。语言的权值是其中所有字符串权值的总和。

如果语言中的任意一个字符串都不是另一个字符串的前缀,则称这个语言是前缀无关的。

请构造一个恰好包含 nn 个不同非空字符串的前缀无关语言,使语言的权值最小。你只需要输出这个最小权值,不需要输出字符串本身。

例如,字母 a、b 的权值分别是 22、55 时,集合 {b, aa, ab} 前缀无关,权值为 5+4+7=165+4+7=16;它是包含三个字符串的最轻前缀无关语言。

输入格式

第一行两个整数 n,kn,k,2≤n≤100002\le n\le10000,2≤k≤262\le k\le26。

第二行 kk 个正整数,第 ii 个数表示第 ii 个字母的权值。每个权值都不超过 1000010000。

输出格式

输出一个整数,表示符合要求的语言的最小权值。

样例输入

3 2
2 5

样例输出

16