Barr the Bear and Kang the Penguin are criminal masterminds. Recently, they heard of a wonderful money-churning machine. This machine runs a game that can be played by two players.
Firstly, the machine gives you a number string A consisting of 2*N digits. Then, any player can choose to remove the leftmost digit of A and append it to his current number as his rightmost digit. This continues until there are no more digits in A. Each player can remove exactly N digits from A. This means that the number strings for each player is N digits long.
When the game ends, each player will earn money equal to the value of his number string. Leading zeroes are allowed.
Note: For more info, see sample input and output.
Barr the Bear and Kang the Penguin want to earn as much money as possible. Help them work out what is the maximum total amount of money they can earn.
The first line contains a number N (1 ≤ N ≤ 19). The next line contains a string with length 2*N digits. Each character of the string will be a digit between 0 and 9 (inclusive).
Output the maximum amount of money they can earn.
Here is one possible Solution.
Let K means that Kang the Penguin takes the digit and B means that Barr the Bear takes the digit. Then, the digits can be distributed the following way.
This way, Kang the Penguin will get the number string "234" and Barr the Bear will get the number string "001". The sum of these two numbers is 235. This is the maximum value they can earn.