GRE - GRE Words

题意翻译

给出 n 个单词 (n <= 20000) ,每个单词由一些小写字母组成,现在这些单词按照输入的顺序给定,每个单词还有一个权值,当然可能出现某个单词出现了两次,即两个串完全一样但是多次出现,权值还可能不同。你可以将这 n 个单词删掉一些之后,如果剩下的单词满足按照原本输入的顺序排列,上面一个是下面一个的子串,这种删除方法是合法的,求在所有合法的删除方案中剩下的单词的权值和最大是多少? 输入第一行为数据组数,每组数据第一行为 n 的大小,接下来 n 行,每行一个单词。保证输入的单词总长度不超过 30W translated by gzy

题目描述

![](https://cdn.luogu.com.cn/upload/vjudge_pic/SP9941/ed2c106f86e6f13dd6fa1b849ef2a65782a89f48.png)

输入输出格式

输入格式


The first line contains an integer **T** (1 ≤ **T** ≤ 50), indicating the number of test cases. Each test case contains several lines. The first line contains an integer **N** (1 ≤ **N** ≤ 2×10 $ ^{4} $ ), indicating the number of words. Then **N** lines follows, each contains a string **S** $ _{i} $ and an integer **W** $ _{i} $ , representing the word and its importance. **S** $ _{i} $ contains only lowercase letters. You can assume that the total length of all words will not exceeded 3×10 $ ^{5} $ .

输出格式


For each test case in the input, print one line: "Case #X: Y", where **X** is the test case number (starting with 1) and **Y** is the largest importance of the remaining sequence of words.

输入输出样例

输入样例 #1

1
5
a 1
ab 2
abb 3
baba 5
abbab 8

输出样例 #1

Case #1: 14