题目背景

给一个操作序列，每次操作一条蛇（头往前一格或者尾巴往前一格），蛇不能相交。求数轴上最小多大范围能使得蛇完成所有操作？

题目描述

假设你在玩一个游戏，游戏场地看起来像是由 $1 \times 10^9$ 个正方形单元格组成的长条，编号从 $1$ 到 $10^9$ 。

你有 $n$ 条蛇(编号从 $1$ 到 $n$ )需要放进一些单元格中。一开始，每条蛇恰好占据一个单元格，而且一个单元格中不能放入超过一条蛇。之后，游戏开始。

游戏持续 $q$ 秒。每秒可能发生两种事件：

• 蛇 $s_i$ 变大：如果蛇 $s_i$ 占据了单元格 $[l, r]$ ，它会变大到单元格 $[l, r + 1]$ ；
• 蛇 $s_i$ 缩小：如果蛇 $s_i$ 占据了单元格 $[l, r]$ ，它会缩小到单元格 $[l + 1, r]$ 。

如果在任何时刻，任何一条蛇撞到了障碍物(另一条蛇或范围的边界)，那么你就输了。否则，你就赢了，分数等于结束时被占据的最大的单元格编号。

你能获得的最低分数是多少？

输入格式

第一行包含两个整数 $n$ 和 $q$ ( $1 \le n \le 20$ ; $1 \le q \le 2 \cdot 10^5$ )表示蛇的数量和事件的数量。接下来的 $q$ 行包含事件描述。

第 $i$ 行包含以下两种情况之一

• $s_i\quad+$（ $1 \le s_i \le n$ ），意思是第 $s_i$ 条蛇变大。
• $s_i\quad-$（ $1 \le s_i \le n$ ），意思是第 $s_i$ 条蛇变小。

输入保证长度为 $1$ 的蛇永远不会缩小。

输出格式

输出一个整数表示可能的最低分数。

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

11

说明/提示

对于 $30 \%$ 的数据：$1\le n\le 9,1\le q\le 100$

对于 $60 \%$ 的数据：$1\le n\le 9,1\le q\le 2\times 10^5$

对于 $100 \%$ 的数据：$1\le n\le 20,1\le q\le 2\times 10^5$