题目描述

给定一颗 $n$ 个节点的 trie 树，以 $1$ 号节点为根，其余每个节点到父亲的边上都有一个字符，且父亲相同的节点到父亲的边上的字符互不相同。从根到每个节点的路径都代表一个单词，这个单词由路径上的字符顺序拼接而成。在每个节点 $i$ 处有一个权值 $c_i$，表示该节点所代表的单词需要写出的次数。

你有一个 cache，可以选择任意个单词放在 cache 里面。写单词时，每写一个字符需要花费 $a$ 的代价。当写出一个完整的单词时，就可以选择结束当前单词，转而拼写下一个单词。而 cache 会根据当前已经写出的字符，把 cache 中以这一部分字符为前缀且字典序最小的单词提示出来。此时你可以花费 $b$ 的代价直接写出这个单词，并结束当前单词的拼写，转而拼写下一个单词。注意一个字符串本身也看作它自己的前缀。

求完成 trie 树上所有单词的拼写所需的最小代价。

输入格式

第一行输入三个整数 $n,a,b$ $(1\leq n\leq 2\times 10^5,0\leq a,b\leq 10^4)$，分别表示 trie 树的大小、写一个字符的代价和使用 cache 写出单词的代价。

接下来 $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$ 个节点到儿子节点的边上的字符之间的字典序从小到大依次给出。

保证 $c_1=0$。

输出格式

输出一行一个整数，表示完成 trie 树上所有单词的拼写所需的最小代价。

4 2 3
0 2 3 2
3 0
2 1 4
4 0

22

提示

【样例解释】

假设每个节点的子节点按字典序从小到大按 $a,b,\ldots$ 编码。最优方案为将 $aa$ 放在 cache 中，于是 $aa$ 可以花费 $3\times 4$ 的代价利用提示打出来，$a$ 和 $b$ 都直接打出来。总代价为 $3\times 4+2\times 1\times 2+2\times 1\times 3=22$。