B. 深界六层-交换的代价

    传统题 1000ms 256MiB

深界六层-交换的代价

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

来去无回之都

“若你愿继续向深处前行…… 那便做好被剥夺的觉悟吧。 因为在这里,‘价值’比生命更真实。” ——探窟者的无名遗言


“欢迎来到生骸村…… 在这里,你的身体就是货币, 你的渴望,就是我们收割的果实。” ——生骸村的低语

在深渊第六层「来无回之都」的隐秘深处, 坐落着由生骸们组成的村庄——Ilblu:生骸村。

这里没有上升负荷,却执行着更加残酷的代价法则:

任何所求之物,都必须用等价的身体部位来交换。

为了继续旅程,莉可、雷格与娜娜奇必须在村中的“价值交换所” 用自身的身体部位换取补给与情报。

交换所摆出了一张 nn 行 mm 列 的身体部位目录:

  • value[i][j]value[i][j]:献出该部位承受的痛苦代价
  • part[i][j]part[i][j]:该部位所属的类别(A−ZA-Z / a−za-z,大小写视为同类)

生骸村提出了 TT 次交易: 每次给出一个字符串 SS(字符为 A–ZA–Z 或 a–za–z),表示需求的类别。

例如:

  • "A""A":需要 11 件 AA 类物品
  • "AB""AB":需要 11 件 AA 类 + 11 件 BB 类物品
  • "AAA""AAA":需要 33 件 AA 类物品

每个身体部位只能使用一次,且只能换取一件物品。

你的任务是:

对每次交易,求最小总代价;若某类别数量不足则输出 -1。


输入格式

第一行输入两个整数n,m(1≤n,m≤100)n, m(1 \le n, m \le 100)。

接下来 nn 行:每行输入mm个整数valuei,j(1≤valuei,j≤109)value_{i,j}(1 \le value_{i,j} \le 10^9)

接下来 nn 行,每行 输入mm 个字符parti,j(1≤parti,j≤109)part_{i, j}(1 \le part_{i, j} \le 10^9),字符为 A–ZA–Z 或 a–za–z(大小写视为同一类别)

接下来输入一行一个整数T(1≤T≤100)T(1 \le T \le 100)。

接下来 TT 行,每行输入一个由大写字母组成的字符串S(1≤∣S∣≤100)S(1 \le |S| \le 100)

输出格式

对每一次询问,输出一行一个整数:

  • 若可以满足需求,输出最小总代价
  • 若无法满足,输出 -1

样例

3 3
10 20 30
5 15 25
8 12 40
Aab
BcC
dDa
3
A
AB
AAA
10
15
70

2025级新生训练·附加题

未参加
状态
已结束
规则
XCPC
题目
9
开始于
2025-11-26 18:30
结束于
2025-11-26 21:30
持续时间
3 小时
主持人
参赛人数
126