关于求解指定长度回文咒语最小构建成本的技术问询

回文战士（Paladrome）是源自圣骑士（Paladin）的特殊战士阶层，擅长神圣魔法。圣骑士要晋升为回文战士，需构造特殊咒语——该咒语必须是回文字符串（正读反读完全相同）。构建咒语的成本基于最终咒语中出现的符文对（相邻字母）的成本，未在输入中给出的符文对不允许使用。咒语总成本为所有出现的符文对成本之和。

若咒语为abbaacaabba，则成本为ab + ba + ac + ca + ab + ba的成本总和。

确定构造指定长度的回文咒语的最小成本。

• 第一行包含两个整数n（1 ≤ n ≤ 676）和k（2 ≤ k ≤ 100）：n为符文对数量，k为咒语的符文（字母）长度。
• 接下来n行每行包含一个长度为2的小写字母字符串s（符文对）和整数c（1 ≤ c ≤ 100），表示该符文对的成本，所有符文对互不相同。

输出一个整数，即构造长度为k的回文咒语的最小可能成本；若无法构造则输出-1。

5 9  
ab 4  
ba 1  
bd 3  
db 100  
bc 4  

20

我完全搞不懂这个问题，不知道该从哪里开始求解。

内容的提问来源于stack exchange，提问作者potatokid432