Finally, at the end of the day, it is time for a well-deserved snack. Rar the Cat opens up the pack of green beans he has been keeping all day. However, instead of a pack of beautiful green beans, he finds mud overflowing out of the bag! Oh no! Carefully, he lays out the green beans and mud balls on the table in one line. Since the green beans are all dirty, he has decided to play a game with Kang the Penguin using the dirty green beans and mud.
There are N green beans and mud balls on the table. A green bean with a diameter of D mm will garner Rar the Cat D points. However, a mud ball will decrease Rar the Cat's total points by 2. To win the game, Rar the Cat has to find a consecutive section within the line of green beans and mud balls that can garner him the most points.
Write a program that, when given the profile of the line of green beans and mud balls, outputs the maximum number of points Rar the Cat can get from this game.
The first line of input will contain one integer, N.
The second line of input will contain N characters, containing one of these:
- a number from '1' to '9', indicating a green bean with that size.
- 'M', indicating a mudball
Your output should contain one integer, the maximum number of points Rar the Cat can get from this game.
Your output should end with a newline.
Subtask 1 (30%): 1 <= N <= 100
Subtask 2 (70%): 1 <= N <= 1 000 000