Робот-пылесос
(Время: 2 сек. Память: 128 Мб Сложность: 54%)
Рассмотрим координатную плоскость, которую планируется очищать с использованием робота-пылесоса. Робот-пылесос представляет собой квадрат размером k×k со сторонами, параллельными осям координат. Изначально левый нижний угол робота находится в точке (0, 0), а правый верхний, соответственно – в точке (k, k).
Вам дана последовательность из n перемещений робота по плоскости, i-е перемещение характеризуется направлением di, принимающим значения 'N' (вверх, увеличение координаты Y ), 'S' (вниз, уменьшение координаты Y ), 'W' (влево, уменьшение координаты X) или 'E' (вправо, увеличение координаты X), и целым числом ai – расстоянием, на которое робот перемещается.
На рисунке приведены примеры возможных перемещений робота в каждом направлении.
Робот в каждый момент времени убирает всю площадь под собой. Иными словами, точка считается убранной тогда и только тогда, когда она в какой-то момент времени принадлежала квадрату размера k×k, на котором находился робот.
По заданным перемещениям робота посчитайте суммарную площадь всей убранной поверхности.
Входные данные
В первой строке входного файла INPUT.TXT через пробел даны два целых числа: размер робота k и количество команд
n (1 ≤ k ≤ 104; 1 ≤ n ≤ 105).
В i-й из следующих n строк через пробел даны направление i-го перемещения di и его расстояние ai (di – буква 'N', 'S', 'W' или 'E'; 1 ≤ ai ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите суммарную площадь убранной роботом поверхности.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1 5
E 2
N 2
W 4
S 4
E 4 | 17 |
| 2 | 3 4
W 2
N 1
W 1
N 2 | 27 |
Пояснения к примерам
Ниже приведены иллюстрации к перемещениям робота согласно примерам из условия. Клетки, которые робот посетил за время своих перемещений, затемнены.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
