URI Online Judge | 2952

Sustainable Living

By Samuel Eduardo da Silva, IFSULDEMINAS/UFF BR Brazil

Timelimit: 1

Oliveira is a boy who loves online games. One of his favorites is "A Vida Sustentável", in which he controls a puppet who must live a sustainable life, following daily actions that do not compromise the sustainability of his world. He is the only character in the game, because the purpose of it is to show how our activities affect the world around us. Among the main activities performed in the game, he can eat a variety of foods and use some types of vehicles. These two activities compromise two indicators of your world, the amount of usable water remaining (in relation to your food) and the amount of gases that the ozone layer can withstand (in relation to your means of transport), but they guarantee nutrition or speed to your character. For this problem, we will use the following tables, which relate food to water consumption and vehicles to gas emission, in addition to include the nutrition of each food and the speed of each vehicle:

Oliveira realized that there was a cost benefit for each food and vehicle. For example, the cost benefit of the car would be -20 as it emits 100 gas but provides 80 speed and the corn would be 650 as it consumes 450 water but provides 1000's of nutrition. One day in this game has N hours, and the player can play for up to N hours the game. Oliveira always starts playing at some random time on the day of game play and finishes playing after a few hours, no more than N, and every hour played, his character either ate or used a vehicle. For example, if the game has 10 hours, Oliveira could start at 7 o'clock and play until the 6 o'clock, stopping sooner. After looking at a report of your actions, I'd like to know how much time intervals (vector continuum) have had a higher and lower cost benefit so you can analyze these intervals and try to better balance your actions the next time you go play. The hours that Oliveira does not play should not be considered for the solution, if there are only hours in which he did not play, the answer is 0 0.

Input

The first line of the entry contains an integer N(0 < N ≤ 100000) that indicates the amount of hours of a day in the game. The following are N characters indicating Oliveira's actions for each hour. Limits: 0 <N ≤ 100000; Each character can be:
● A, for Rice;
● C, for Meat;
● S, for Soy;
● P, for Plockt;
● M, for Corn;
● K, for Car;
● B, for Bicycle
● N, when, at this time, Oliveira did not play.

Basically, what marks the first hour played is the first occurrence of a character other than 'N' after one that is or if the first hour is no longer 'N'.

Output

2 integers, indicating the value of the largest cost benefit interval, and the lowest cost benefit range, respectively.

Input Samples Output Samples

7
A C S P M K B

13770 -13550

3
C N C

-13500 -27000