{"raw_statement":[{"iden":"statement","content":"给定一颗 $n$ 个节点的 trie 树，以 $1$ 号节点为根，其余每个节点到父亲的边上都有一个字符，且父亲相同的节点到父亲的边上的字符互不相同。从根到每个节点的路径都代表一个单词，这个单词由路径上的字符顺序拼接而成。在每个节点 $i$ 处有一个权值 $c_i$，表示该节点所代表的单词需要写出的次数。\n\n你有一个 cache，可以选择任意个单词放在 cache 里面。写单词时，每写一个字符需要花费 $a$ 的代价。当写出一个完整的单词时，就可以选择结束当前单词，转而拼写下一个单词。而 cache 会根据当前已经写出的字符，把 cache 中以这一部分字符为前缀且字典序最小的单词提示出来。此时你可以花费 $b$ 的代价直接写出这个单词，**并结束当前单词的拼写**，转而拼写下一个单词。注意一个字符串本身也看作它自己的前缀。\n\n求完成 trie 树上所有单词的拼写所需的最小代价。"},{"iden":"input","content":"第一行输入三个整数 $n,a,b$ $(1\\leq n\\leq 2\\times 10^5,0\\leq a,b\\leq 10^4)$，分别表示 trie 树的大小、写一个字符的代价和使用 cache 写出单词的代价。\n\n接下来 $n$ 行，其中第 $i$ 行首先输入两个整数 $c_i,k_i$ $(0\\leq c_i\\leq 10^4,0\\leq k_i<n)$，分别表示第 $i$ 个节点上的权值和第 $i$ 个节点的儿子节点的个数。接下来输入 $k_i$ 个整数 $son_{i,1},son_{i,2},\\ldots,son_{i,k_i}$，表示第 $i$ 个节点的儿子节点编号，按照第 $i$ 个节点到儿子节点的边上的字符之间的字典序从小到大依次给出。\n\n保证 $c_1=0$。"},{"iden":"output","content":"输出一行一个整数，表示完成 trie 树上所有单词的拼写所需的最小代价。"},{"iden":"note","content":"**【样例解释】**\n\n假设每个节点的子节点按字典序从小到大按 $a,b,\\ldots$ 编码。最优方案为将 $aa$ 放在 cache 中，于是 $aa$ 可以花费 $3\\times 4$\n的代价利用提示打出来，$a$ 和 $b$\n都直接打出来。总代价为 $3\\times 4+2\\times 1\\times 2+2\\times 1\\times 3=22$。"}],"translated_statement":null,"sample_group":[["4 2 3\n0 2 3 2\n3 0\n2 1 4\n4 0","22"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}