G. Snakes

设想一个游戏，场地是由 这样的方格组成的长条，每个方格用从 到 的编号表示。

你要在这些方格中放置 条蛇（编号为 到 ）。起初，每条蛇仅占据一个方格，且每个方格不能被多条蛇同时占用。在完成初始放置之后，游戏正式开始。

游戏会持续 秒。在每一秒，有两种可能的事件：

• 蛇 变长：如果蛇 占据了方格区间 ，它会向右扩展，变成占据区间 ；
• 蛇 缩短：如果蛇 占据了方格区间 ，它会向左收缩，变成占据区间 。

每秒钟只会发生其中一种事件。

如果任何时间点有蛇碰到了障碍物（其它蛇或方格带的边界），你将立刻输掉游戏。否则，你的得分则等于所有蛇所占领的最大方格编号。

问题是，你能让最终得分最低是多少？

第一行包含两个整数 和 ，表示蛇的数量和事件的数量（；）。接下来的 行每行描述一个事件。

第 行包含：

• " +"，表示第 条蛇扩展；
• " -"，表示第 条蛇收缩。

给出的事件序列是有效的，即任何长度为 的蛇都不会收缩。

输出一个整数，表示你可以取得的最低得分。

输入 #1

3 6
1 +
1 -
3 +
3 -
2 +
2 -

输出 #1

4

输入 #2

5 13
5 +
3 +
5 -
2 +
4 +
3 +
5 +
5 -
2 +
3 -
3 +
3 -
2 +

输出 #2

11