28410번 - Робот-пылесос 서브태스크다국어

Рассмотрим координатную плоскость, которую планируется очищать с использованием робота пылесоса. Робот-пылесос представляет собой квадрат размером $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$).

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

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