你在为一门极少见的语言做专用分词。语言学家给出了一个“小词典”，每个条目都有一个分值，表示该词单独成词的合理性强弱。 同时，还收集了“相邻词对”的转移加分：当上一个词与下一个词按某种搭配出现时，整体会多（或少）一些分数。 你的目标是在给定的连续小写字母串中，切分出一条完整的词序列，使“词典分+转移加分”的总和最大。如果无法用词典完全覆盖整串，则输出0。
输入描述:
第一行：文本串 text，仅含小写英文字母。第二行：整数 n，表示词典条目数。接下来 n 行：每行一个词与其分值，中间用空格分隔。接下来一行：整数 m，表示转移加分条目数。接下来 m 行：每行包含“前词 后词 加分”，三者以空格分隔，加分可为负。


输出描述:
一行，一个整数：最大可获得的总分。如果不存在任何完整切分，输出0。
示例1

输入

aababa
4
a 1
aa 3
ab 2
ba 2
3
aa ba 2
ba ba -1
ab a 1

输出

8

说明

  • 最优切分：aa | ba | ba
    • 词典分：3 + 2 + 2 = 7
    • 转移分：aa→ba = +2，ba→ba = -1
    • 总分：7 + 2 - 1 = 8
  • 其他可行切分（例如：a | ab | a | ba）
    • 词典分：1 + 2 + 1 + 2 = 6
    • 转移分：ab→a = +1（其余未命中）
    • 总分：6 + 1 = 7
      因此最优答案为 8。

备注:
本题由牛友@Charles 整理上传
加载中...