CF2051G 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$。 **本翻译由 AI 自动生成**

In the first test, the optimal strategy is to place the second snake at cell $ 1 $ , the third snake — at $ 2 $ , and the first one — at $ 3 $ . The maximum occupied cell is cell $ 4 $ , and it's the minimum possible score. In the second test, one of the optimal strategies is to place: - snake $ 2 $ at position $ 1 $ ; - snake $ 3 $ at position $ 4 $ ; - snake $ 5 $ at position $ 6 $ ; - snake $ 1 $ at position $ 9 $ ; - snake $ 4 $ at position $ 10 $ .