Задача 3. Робот-пылесос ≡
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
| Максимальный балл: | 100 |
Условие
Рассмотрим координатную плоскость, которую планируется очищать с использованием робота пылесоса. Робот-пылесос представляет собой квадрат размером k × k со сторонами, параллельными осям координат. Изначально левый нижний угол робота находится в точке (0, 0), а правый верхний, соответственно — в точке (k, k).
Вам дана последовательность из n перемещений робота по плоскости, i-е перемещение характеризуется направлением di, принимающим значения N (вверх, увеличение координаты Y), S (вниз, уменьшение координаты Y), W (влево, уменьшение координаты X) или E (вправо, увеличение координаты X), и целым числом ai — расстоянием, на которое робот перемещается.
Робот в каждый момент времени убирает всю площадь под собой. Иными словами, точка считается убранной тогда и только тогда, когда она в какой-то момент времени принадлежала квадрату размера k × k, на котором находился робот.
По заданным перемещениям робота посчитайте суммарную площадь всей убранной поверхности.
Формат входных данных
В первой строке ввода через пробел даны два целых числа: размер робота k и количество команд n.
В i-й из следующих n строк через пробел даны направление i-го перемещения di и его расстояние ai (di — буква N, S, W или E).
Формат выходных данных
Выведите суммарную площадь убранной роботом поверхности.
Ограничения
1 ≤ k ≤ 104; 1 ≤ n ≤ 105
1 ≤ ai ≤ 109
Система оценки
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| 1 | 9 | k = 1, n ≤ 10, ai ≤ 10 | первая ошибка | |
| 2 | 10 | k ≤ 10, n ≤ 10, ai ≤ 100 | 1 | первая ошибка |
| 3 | 11 | k ≤ 1000, n ≤ 1000, ai = 1 | первая ошибка | |
| 4 | 8 | k ≤ 104, n ≤ 105, ai = k | первая ошибка | |
| 5 | 14 | k = 1, n ≤ 1000, ai ≤ 109 | 1 | первая ошибка |
| 6 | 15 | k ≤ 104, n ≤ 1000, ai ≤ 109 | 1 − 3, 5 | первая ошибка |
| 7 | 16 | k = 1, n ≤ 105, ai ≤ 109 | 1, 5 | первая ошибка |
| 8 | 17 | k ≤ 104, n ≤ 105, ai ≤ 109 | 1 − 7 | первая ошибка |
Пояснение к примеру
Ниже приведены иллюстрации к перемещениям робота согласно примерам из условия. Клетки, которые робот посетил за время своих перемещений, затемнены.
Примеры тестов
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|