A90649.Snakes

设想一个游戏，场地是由 $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$ +"，表示第 $s_i$ 条蛇扩展；
• " $s_i$ -"，表示第 $s_i$ 条蛇收缩。

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

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

在第一个例子中，最优策略是将第二条蛇放在方格 $1$，第三条蛇放在方格 $2$，第一条蛇放在方格 $3$。最终，最大的被占用方格是方格 $4$，这是最低可能得分。

在第二个例子中，一种最优的放置策略是：

• 把第 $2$ 条蛇放在位置 $1$；
• 将第 $3$ 条蛇放在位置 $4$；
• 将第 $5$ 条蛇放在位置 $6$；
• 将第 $1$ 条蛇放在位置 $9$；
• 将第 $4$ 条蛇放在位置 $10$。