G. Typing
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Given a trie tree with $$$n$$$ nodes, with node $$$1$$$ as the root, and each node has a character on the edge to its parent, and the characters on the edges to the same parent are all different. The path from the root to each node represents a word, which is formed by concatenating the characters on the path. At each node $$$i$$$, there is a weight $$$c_i$$$, indicating the number of times the word represented by that node needs to be written.

You have a cache, and you can choose any number of words to put in the cache. When writing a word, it costs $$$a$$$ for each character. When a complete word is written, you can choose to end the current word and start spelling the next word. The cache will always suggest the word with the smallest lexicographical order that has the current written characters as a prefix, and at this point, you can spend $$$b$$$ to directly write out this word, and end the spelling of the current word, and start spelling the next word. Note that a string itself is also considered as its own prefix.

Find the minimum cost required to complete the spelling of all words on the trie tree.

Input

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 tree, the cost of writing a character, and the cost of using the cache to write a word.

Next $$$n$$$ lines, where the $$$i$$$-th line first contains two integers $$$c_i,k_i$$$ ($$$0\leq c_i\leq 10^4,0\leq k_i \lt n$$$), representing the weight of the $$$i$$$-th node and the number of child nodes of the $$$i$$$-th node. Next, input $$$k_i$$$ integers $$$son_{i,1},son_{i,2},\ldots,son_{i,k_i}$$$, representing the numbers of the child nodes of the $$$i$$$-th node, given in increasing order of lexicographical order between the characters on the edge from the $$$i$$$-th node to the child nodes.

It is ensured that $$$c_1=0$$$.

Output

Output a single integer, representing the minimum cost required to complete the spelling of all words on the trie tree.

Example
Input
4 2 3
0 2 3 2
3 0
2 1 4
4 0
Output
22
Note

The explanation to the sample test case is as follows.

Assume that the edges to the child nodes of each node are encoded by $$$a,b,\ldots$$$ in lexicographic order from small to large. The optimal solution is to put $$$aa$$$ in the cache, so $$$aa$$$ can be typed out using prompts at a cost of $$$3\times 4$$$, and both $$$a$$$ and $$$b$$$ are typed out directly. The total cost is $$$3\times 4+2\times 1\times 2+2\times 1\times 3=22$$$.