Problem Description

You are given a trie with $n$ nodes, rooted at node $1$. For every other node, the edge from its parent to it has a character, and for nodes with the same parent, these characters are all different. The path from the root to each node represents a word, formed by concatenating the characters on the path in order. Each node $i$ has a weight $c_i$, meaning the word represented by this node needs to be written $c_i$ times.

You have a cache, and you may choose any number of words to store in the cache. When writing a word, typing one character costs $a$. After finishing a complete word, you may choose to end the current word and start spelling the next word. The cache will, based on the characters you have already typed, suggest the lexicographically smallest word in the cache that has this typed string as a prefix. At this time, you may pay cost $b$ to directly output this word, and end the spelling of the current word, then start spelling the next word. Note that a string is also considered a prefix of itself.

Find the minimum total cost to finish spelling all words on the trie.

Input Format

The first line contains three integers $n,a,b$ $(1\leq n\leq 2\times 10^5,0\leq a,b\leq 10^4)$, representing the size of the trie, the cost to type one character, and the cost to output a word using the cache.

Then follow $n$ lines. On the $i$-th line, the input first contains two integers $c_i,k_i$ $(0\leq c_i\leq 10^4,0\leq k_i<n)$, representing the weight on node $i$ and the number of children of node $i$. Then follow $k_i$ integers $son_{i,1},son_{i,2},\ldots,son_{i,k_i}$, representing the indices of the children of node $i$, given in increasing lexicographical order of the characters on the edges from node $i$ to these children.

It is guaranteed that $c_1=0$.

Output Format

Output one integer in one line, representing the minimum cost to finish spelling all words on the trie.

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

22

Hint

[Sample Explanation]

Assume the children of each node are encoded as $a,b,\ldots$ in increasing lexicographical order. The optimal strategy is to put $aa$ into the cache. Then $aa$ can be typed using suggestions at a cost of $3\times 4$, while $a$ and $b$ are typed directly. The total cost is $3\times 4+2\times 1\times 2+2\times 1\times 3=22$.

Translated by ChatGPT 5