PROBLEM STATEMENT
Mr. Dengklek lives in the Kingdom of Ducks, where humans and ducks live together in peace and 
harmony. 



Mr. Dengklek works as a chain maker. Today, he would like to make a beautiful chain as a 
decoration for one of his lovely ducks. He will produce the chain from leftovers he found in his 
workshop. Each of the leftovers is a chain piece consisting of exactly 3 links. Each link is 
either clean or rusty. Different clean links may have different degrees of beauty.



You are given a vector <string> chains describing the leftovers. Each element of chains is a 
3-character string describing one of the chain pieces. A rusty link is represented by a period 
('.'), whereas a clean link is represented by a digit ('0'-'9'). The value of the digit in the 
clean link is the beauty of the link. For example, chains = {".15", "7..", "532", "..3"} means 
that Mr. Dengklek has 4 chain pieces, and only one of these ("532") has no rusty links.



All links have the same shape, which allows Mr. Dengklek to concatenate any two chain pieces. 
However, the link shape is not symmetric, therefore he may not reverse the chain pieces. E.g., in 
the above example he is able to produce the chain "532.15" or the chain ".15..37..", but he cannot 
produce "5323..".



To produce the chain, Mr. Dengklek will follow these steps:

Concatenate all chain pieces in any order.
Pick a contiguous sequence of links that contains no rusty links. Remove and discard all the 
remaining links.

The beauty of the new chain is the total beauty of all the links picked in the second step. Of 
course, Mr. Dengklek would like to create the most beautiful chain possible.



Return the largest possible beauty a chain can have according to the above rules.

DEFINITION
Class:DengklekMakingChains
Method:maxBeauty
Parameters:vector <string>
Returns:int
Method signature:int maxBeauty(vector <string> chains)


NOTES
-Mr. Dengklek is not allowed to remove and discard individual links before concatenating the chain 
pieces.
-If all links in the input are rusty, Mr. Dengklek is forced to select an empty sequence of links. 
The beauty of an empty sequence is 0.


CONSTRAINTS
-chains will contain between 1 and 50 elements, inclusive.
-Each element of chains will contain exactly 3 characters.
-Each character in each element of chains will be either a '.' or one of '0'-'9'.


EXAMPLES

0)
{".15", "7..", "402", "..3"}

Returns: 19

One possible solution:


In the first step, concatenate the chain pieces in the order "..3", ".15", "402", "7.." to obtain 
the chain "..3.154027..".
In the second step, pick the subsequence "154027".

The beauty of the chain in this solution is 1+5+4+0+2+7 = 19.

1)
{"..1", "7..", "567", "24.", "8..", "234"}

Returns: 36

One possible solution is to concatenate the chain pieces in this order:

"..1", "234", "567", "8..", "24.", "7.." -> "..12345678..24.7..",

and then to pick the subsequence "12345678". Its beauty is 1+2+3+4+5+6+7+8 = 36.

2)
{"...", "..."}

Returns: 0

Mr. Dengklek cannot pick any links.

3)
{"16.", "9.8", ".24", "52.", "3.1", "532", "4.4", "111"}

Returns: 28



4)
{"..1", "3..", "2..", ".7."}

Returns: 7



5)
{"412", "..7", ".58", "7.8", "32.", "6..", "351", "3.9", "985", "...", ".46"}

Returns: 58



 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.