【题目背景】

有的人在匹配，有的人在匹配。

【题目描述】

有一个长度为 n 的字符串 S，和一个长度为 n 的数列 wi，你需要 保留 S 的 k 个位置，其余位置两两匹配。

记 (i, j) 表示位置 i 和位置 j 的匹配。

要求满足对于所有匹配 (i, j)，都有 $S_i!= S_j$。

一个匹配 (i, j) 的价值是$100 × |i − j| + w_i + w_j$。

求满足条件的方案的最小价值。你只需要输出这个价值。如果没有满足条件的方案，输出 −1。

【输入格式】

从文件 match.in 中读入数据。

第一行一个字符串 S。

第二行 n 个正整数$w_1,w_2,\dots,w_n$。

第三行一个非负整数 k。

【输出格式】

输出到文件 match.out 中。

一行一个整数表示答案。如果无解请输出 −1。

【样例 1 输入】

aabcde
1 100000 100000 100000 100000
3 2

【样例 1 输出】

200402

【样例 1 解释】

一种可行的匹配方案是$ {(1, 3),(2, 4)}$，代价是 $(100 × |1 − 3| + 1 + 100000) + (100 × |2 − 4| + 1 + 100000)$。

另一种可行的匹配方案是 ${(1, 4),(2, 3)}$，代价是 $(100×|1−3|+1+100000)+ (100× |2 − 4| + 1 + 100000)$。

注意到 ${(1, 2),(3, 4)}$ 是不可行的，因为 $S_1 = S_2 = a$。

【样例 2】

见选手目录下的$ match/match2.in$ 与$ match/match2.ans$。

该样例约束与子任务 1 相同。

【样例 3】

见选手目录下的$ match/match3.in$ 与$ match/match3.ans$。

该样例约束与子任务 2 相同。

【样例 4】

见选手目录下的 $match/match4.in $与 $match/match4.ans$。

该样例约束与子任务 3 相同。

【样例 5】

见选手目录下的 $match/match5.in $与$ match/match5.ans$。

该样例约束与子任务 6 相同。

【测试点约束】

对于所有数据，保证$ 2 ≤ n ≤ 2500, 0 ≤ k ≤ 6, 1 ≤ w_i ≤ 105, Si ∈$ { $a, b, c, d, e, f$ }$ , n ≡ k (mod 2)。$

• 子任务 1（10 分）：$n ≤ 10$。

• 子任务 2（10 分）：$n ≤ 30$。

• 子任务 3（20 分）：$n ≤ 100$。

• 子任务 4（20 分）：$S_i$ ∈ { $a, b$ }。

• 子任务 5（15 分）：$k = 0$。

• 子任务 6（25 分）：无特殊限制。