Рассмотрим координатную плоскость, которую планируется очищать с использованием робота пылесоса. Робот-пылесос представляет собой квадрат размером $k \times k$ со сторонами, параллельными осям координат. Изначально левый нижний угол робота находится в точке $(0, 0)$, а правый верхний, соответственно — в точке $(k, k)$.

Вам дана последовательность из n перемещений робота по плоскости, $i$-е перемещение характеризуется направлением $d_i$ , принимающим значения N (вверх, увеличение координаты $Y$), S (вниз, уменьшение координаты $Y$), W (влево, уменьшение координаты $X$) или E (вправо, увеличение координаты X), и целым числом $a_i$ — расстоянием, на которое робот перемещается.

На рисунке приведены примеры возможных перемещений робота в каждом направлении.

Робот в каждый момент времени убирает всю площадь под собой. Иными словами, точка считается убранной тогда и только тогда, когда она в какой-то момент времени принадлежала квадрату размера $k \times k$, на котором находился робот. По заданным перемещениям робота посчитайте суммарную площадь всей убранной поверхности.

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

В первой строке ввода через пробел даны два целых числа: размер робота $k$ и количество команд $n$ ($1 \le k \le 10^4$; $1 \le n \le 10^5$).

В $i$-й из следующих $n$ строк через пробел даны направление $i$-го перемещения $d_i$ и его расстояние $a_i$ ($d_i$ — буква N, S, W или E; $1 \le a_i \le 10^9$).

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

Выведите суммарную площадь убранной роботом поверхности.

Подзадачи