There is a new TV game on BerTV. In this game two players get a number *A* consisting of 2*n* digits. Before each turn players determine who will make the next move. Each player should make exactly *n* moves. On it's turn *i*-th player takes the leftmost digit of *A* and appends it to his or her number *S*_{i}. After that this leftmost digit is erased from *A*. Initially the numbers of both players (*S*_{1} and *S*_{2}) are «empty». Leading zeroes in numbers *A*, *S*_{1}, *S*_{2} are allowed. In the end of the game the first player gets *S*_{1} dollars, and the second gets *S*_{2} dollars.

One day Homer and Marge came to play the game. They managed to know the number *A* beforehand. They want to find such sequence of their moves that both of them makes exactly *n* moves and which maximizes their total prize. Help them.

The first line contains integer *n* (1 ≤ *n* ≤ 18). The second line contains integer *A* consisting of exactly 2*n* digits. This number can have leading zeroes.

提交代码