G. Змейки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Предположим, вы играете в игру, где игровое поле выглядит как полоска из $$$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$$$ +» ($$$1 \le s_i \le n$$$), означающее, что $$$s_i$$$-я змея увеличивается,
  • либо «$$$s_i$$$ -» ($$$1 \le s_i \le n$$$), означающее, что $$$s_i$$$-я змея уменьшается.

Дополнительное ограничение на входные данные: заданная последовательность событий валидна, т. е. змея длиной $$$1$$$ никогда не уменьшается.

Выходные данные

Выведите одно целое число — минимально возможный счет.

Примеры
Входные данные
3 6
1 +
1 -
3 +
3 -
2 +
2 -
Выходные данные
4
Входные данные
5 13
5 +
3 +
5 -
2 +
4 +
3 +
5 +
5 -
2 +
3 -
3 +
3 -
2 +
Выходные данные
11
Примечание

В первом тесте оптимальная стратегия заключается в том, чтобы разместить вторую змею в ячейке $$$1$$$, третью змею — в $$$2$$$, а первую — в $$$3$$$. Максимальная занятая ячейка — ячейка $$$4$$$, и это минимально возможный результат.

Во втором тесте одна из оптимальных стратегий — следующая: нужно поставить

  • змейку $$$2$$$ в позицию $$$1$$$;
  • змейку $$$3$$$ в позицию $$$4$$$;
  • змейку $$$5$$$ в позицию $$$6$$$;
  • змейку $$$1$$$ в позицию $$$9$$$;
  • змейку $$$4$$$ в позицию $$$10$$$.