E. Mixed Economy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bossologist is in a group with $$$N$$$ people (including himself) that has recently won the lottery! Because the group is very fair, they deposit $$$100$$$ dollars into each person's bank account. Everyone is excited to spend their money, but they make sure first to keep track of their purchases in a spending list. The list is of length $$$Q$$$ and contains the purchases of each person and they amount they spent, in chronological order.

However, the person who has the longest consecutive streak of spending must pay a tax of $$$A$$$ dollars to each person in the group, where $$$A$$$ represents the length of the longest consecutive streak. If multiple people have the same longest consecutive streak, the person who got the longest consecutive streak first must pay the tax.

The group wants to know the difference in dollars between the person with most and least amount of money in their bank account after all the purchases are made and taxes are paid. Note that the amount of money in a bank account can be negative.

Input

The first line will include $$$N$$$ ($$$1 \leq N \leq 100$$$), and $$$Q$$$ ($$$1 \leq Q \leq 1000$$$).

The next $$$Q$$$ lines describe the spending list. Each line will include $$$P$$$, the name of the person, and $$$S$$$ ($$$1 \leq S \leq 10^3$$$), how much they spent. Each name will not exceed $$$1000$$$ characters, and furthermore, all $$$N$$$ people will appear at least once on the spending list.

Output

Give the difference, in dollars, between the person with the most and least amount of money in their bank account.

Example
Input
3 7
Bossologist 10
Bossologist 5
Bossologist 20
Codicon 50
Spark 15
Spark 15
Bossologist 5
Output
20
Note

First, each person receives $$$100$$$ dollars in their bank account. In total Bossologist spends $$$40$$$, and so he ends up with $$$60$$$ dollars. Codicon spends a total of $$$50$$$ dollars and so he ends up with $$$50$$$ dollars. And finally Spark spends a total of $$$30$$$ dollars, and so he ends up with $$$70$$$. Now, it's time to pay taxes! Since Bossologist has the highest consecutive streak of $$$3$$$, Bossologist must pay $$$3$$$ dollars to each other person. After paying taxes, Bossologist now has $$$54$$$ dollars, Codicon has $$$53$$$ dollars, and Spark has $$$73$$$ dollars. Spark has the most with $$$73$$$ dollars, and Codicon has the least with $$$53$$$ dollars, so the answer is $$$73 - 53 = 20$$$ dollars.

—

Idea: Spark

Preparation: Spark, Bossologist, Codicon

Occurrences: Novice 5, Intermediate 2