Trie Typing with Cache

You are given a trie with \(n\) nodes. The trie is rooted at node 1. For every node \(i\) (\(1 \le i \le n\)) there is an integer \(c_i\) which denotes that the word represented by the simple path from the root to node \(i\) must be written exactly \(c_i\) times.

For every node other than the root, there is an edge from its parent labelled with a lowercase letter. Moreover, for any node, the characters on the edges to its children are all distinct. Hence the path from the root to a node forms a word (by concatenating the edge characters in order).

You also have a cache into which you may preload an arbitrary set of words (each word is one of the words from the trie). When writing a word, you may type it character–by–character; each character costs \(a\). At any moment during the typing of a word (even before any character is typed, i.e. the prefix is empty) the cache will suggest a word. The suggestion is defined as follows: given the current prefix (which is itself considered a prefix of any word), among all words in the cache that have this prefix, the lexicographically smallest one is suggested. You may choose to pay an extra cost \(b\) to accept the suggestion; if you do so, the suggested word is output in full and the remainder of the current word is filled automatically, and you then move on to the next word.

For each word \(w\) (with length \(|w|\)) that you need to write with frequency \(c\), if you do not put \(w\) into the cache, you have no opportunity to use the suggestion for that word and must type all \(|w|\) characters paying a cost of \(|w| \cdot a\). However, if you decide to put \(w\) into the cache, then when typing it you have two options:

• Type it entirely character–by–character at cost \(|w| \cdot a\), or
• Take advantage of the cache suggestion. The suggestion mechanism works as follows. Suppose the set of words in the cache is \(S\). Let \(w\) be one of these words. If \(w\) is the lexicographically smallest word in \(S\) that has the current prefix P and you have already typed \(P\) (\(P\) can be empty), then you may accept the suggestion by paying cost \(b\); however, to ensure that the suggestion gives you exactly \(w\) (and not some lexicographically smaller word in \(S\) that also has prefix \(P\)), you must type enough characters so that \(w\) becomes the unique candidate. Formally, if \(w\) is the first word in \(S\) in lexicographical order and if there is a word \(u\) in \(S\) that comes immediately before \(w\) (if any), then you can use the suggestion for \(w\) provided that you have typed any prefix \(P = w[0:L]\) with length \(L\) satisfying \[ L \ge \mathrm{LCP}(w, u) + 1,\] where \(\mathrm{LCP}(w, u)\) is the length of the longest common prefix of \(w\) and \(u\) (with the convention that if no such \(u\) exists, take \(\mathrm{LCP}(w,u)=0\)). Then the cost if you use the suggestion is \(L \cdot a + b\). You may choose the prefix length \(L\) (subject to the constraint above) to minimize your cost for typing \(w\).

Your task is to choose a set of words \(S\) (the cache) and a strategy for typing each word so that the total cost for writing all words the required number of times is minimized. Compute and output this minimum total cost.

Note: The cache is established before any word is typed and remains fixed throughout the process.

inputFormat

The first line contains three integers \(n, a, b\) \((1 \le n \le 2000,\ 1 \le a, b \le 10^9)\): the number of nodes in the trie, the cost per character, and the extra cost to accept a cache suggestion.

The following \(n\) lines describe the nodes of the trie in order from 1 to \(n\). The first line describes the root node and contains a single integer \(c_1\) \((0 \le c_1 \le 10^9)\), the frequency of the word corresponding to the root (the empty word). For each node \(i\) from 2 to \(n\), the line contains an integer \(p_i\) (the parent node index, \(1 \le p_i < i\)), a lowercase letter \(ch_i\) (the character on the edge from \(p_i\) to \(i\)), and an integer \(c_i\) \((0 \le c_i \le 10^9)\) representing the frequency that the word corresponding to node \(i\) must be written.

It is guaranteed that for any node, the characters on edges to its children are distinct.

outputFormat

Output a single integer, the minimum total cost required to complete the typing of all words the required number of times.

sample

3 1 1
1
1 a 3
1 b 4

7