假设您玩的游戏中,游戏区域看起来像一条 $$$1 \times 10^9$$$ 方形单元格,编号从 $$$1$$$ 到 $$$10^9$$$。
你有 $$$n$$$ 条蛇(编号从 $$$1$$$ 到 $$$n$$$)需要放入一些单元格中。最初,每条蛇恰好占据一个单元格,并且您不能将多于一条的蛇放入一个单元格中。之后,游戏开始。
游戏持续 $$$q$$$ 秒。每秒可能发生两种类型的事件:
-snake $$$s_i$$$放大:如果snake $$$s_i$$$占据了单元格$$$[l, r]$$$,它会放大为一段$$$[l, r + 1]$$$;
-snake $$$s_i$$$ 收缩:如果snake $$$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$$$ +” ($$$1 \le s_i \le n$$$) 表示第 $$$s_i$$$ 条蛇放大
- 或“$$$s_i$$$ -” ($$$1 \le s_i \le n$$$) 表示第 $$$s_i$$$ 条蛇缩小。
对输入的附加约束:给定的事件序列有效,i。 e.长度为 $$$1$$$ 的蛇永远不会缩小。
输出
打印一个整数——可能的最低分数。
示例
输入 #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
注意
在第一个测试中,最佳策略是将第二条蛇放置在单元格 $$$1$$$ 处,第三条蛇放置在 $$$2$$$ 处,第一条蛇放置在 $$$3$$$ 处。最大占用的单元格是单元格$$$4$$$,并且它是可能的最小分数。
在第二个测试中,最佳策略之一是放置:
- 蛇 $$$2$$$ 位于 $$$1$$$ 位置;
- 蛇 $$$3$$$ 位于 $$$4$$$ 位置;
- 蛇 $$$5$$$ 位于 $$$6$$$ 位置;
- 蛇 $$$1$$$ 位于 $$$9$$$ 位置;
- 蛇 $$$4$$$ 位于 $$$10$$$ 位置。