Eindhoven Marathon Finish Line Crossings

Every year, Eindhoven hosts a marathon. This year, the organizers came up with a special idea – the race never ends after a fixed distance! Instead, the contest is held on a circular track at Eindhoven University, and the runners loop around the track indefinitely.

Anika is one of N participants, numbered from 0 to N - 1. Since she registered quickly, she is participant 0. She starts just after the finish line, while all the other runners start ahead of her. During the race, Anika does not keep track of how many laps she has run, but she does remember the moments when she either overtook someone or was overtaken by someone.

No runner ever goes backwards, and no overtaking happens exactly at the finish line. Also, note that the speeds of the runners are not necessarily constant.

Your task is to determine the minimum number of times Anika must cross the finish line in order for her memories of overtaking events to be possible.

Observation: Every time Anika overtakes another runner, it implies that she has effectively gained one lap over that runner, and every time a runner overtakes her, it implies that her lap difference relative to that runner decreases by one. If we let \[ d = (\text{number of times Anika overtakes someone}) - (\text{number of times someone overtakes Anika}) \] then the minimum number of finish line crossings required is equal to the maximum value of d over all prefixes of the event sequence. (Note that if this value is negative or zero, the answer is 0.)

For example, if the sequence of events is \(+, -, +, +, -\) then the prefix differences are 1, 0, 1, 2, 1. Therefore, the answer is 2, which is the maximum value.

inputFormat

The first line of input contains two integers N and M (1 ≤ N ≤ 10^5, 0 ≤ M ≤ 10^5), where N is the number of participants and M is the number of overtaking events recorded by Anika.

Each of the next M lines contains a single character. The character can be either + or -:

• + means that Anika overtook another runner.
• - means that another runner overtook Anika.

The events are given in the order they occurred.

outputFormat

Output a single integer, the minimum number of times Anika must have crossed the finish line to account for all the overtaking events.

sample

2 1
+

1