P10333 [UESTCPC 2024] 打字

给定一颗 $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

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

**【样例解释】** 假设每个节点的子节点按字典序从小到大按 $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$。