CF237E Build String

You desperately need to build some string $ t $ . For that you've got $ n $ more strings $ s_{1},s_{2},...,s_{n} $ . To build string $ t $ , you are allowed to perform exactly $ |t| $ ( $ |t| $ is the length of string $ t $ ) operations on these strings. Each operation looks like that: 1. choose any non-empty string from strings $ s_{1},s_{2},...,s_{n} $ ; 2. choose an arbitrary character from the chosen string and write it on a piece of paper; 3. remove the chosen character from the chosen string. Note that after you perform the described operation, the total number of characters in strings $ s_{1},s_{2},...,s_{n} $ decreases by 1. We are assumed to build string $ t $ , if the characters, written on the piece of paper, in the order of performed operations form string $ t $ . There are other limitations, though. For each string $ s_{i} $ you know number $ a_{i} $ — the maximum number of characters you are allowed to delete from string $ s_{i} $ . You also know that each operation that results in deleting a character from string $ s_{i} $ , costs $ i $ rubles. That is, an operation on string $ s_{1} $ is the cheapest (it costs $ 1 $ ruble), and the operation on string $ s_{n} $ is the most expensive one (it costs $ n $ rubles). Your task is to count the minimum amount of money (in rubles) you will need to build string $ t $ by the given rules. Consider the cost of building string $ t $ to be the sum of prices of the operations you use.

N/A

N/A

Notes to the samples: In the first sample from the first string you should take characters "b" and "z" with price $ 1 $ ruble, from the second string characters "a", "e" и "b" with price $ 2 $ rubles. The price of the string $ t $ in this case is $ 2·1+3·2=8 $ . In the second sample from the first string you should take two characters "a" with price $ 1 $ ruble, from the second string character "c" with price $ 2 $ rubles, from the third string two characters "a" with price $ 3 $ rubles, from the fourth string two characters "b" with price $ 4 $ rubles. The price of the string $ t $ in this case is $ 2·1+1·2+2·3+2·4=18 $ . In the third sample the solution doesn't exist because there is no character "y" in given strings.