题目描述

译自 ROI Regional 2023 Day1 T3. Робот-пылесос

我们来看一个坐标平面，计划使用机器人吸尘器进行清洁。机器人吸尘器是一个大小为$k \times k$的正方形，边与坐标轴平行。最初，机器人的左下角位于点$(0,0)$，右上角位于点$(k, k)$。

给定机器人在平面上的$n$次移动，第$i$次移动由方向$d_{i}$和距离$a_{i}$描述。方向$d_{i}$可以是$N$（向上，增加$Y$坐标），$S$（向下，减少$Y$坐标），$W$（向左，减少$X$坐标）或$E$（向右，增加$X$坐标），$a_{i}$是移动的距离。

图中展示了机器人在每个方向上的可能移动。 机器人在每一时刻都会清洁其所在的整个区域。换句话说，当某个点在某一时刻属于机器人所在的$k \times k$的正方形时，该点就被清洁了。

根据给定的机器人移动，计算被清洁的总面积。

输入格式

第一行输入包含两个整数：机器人的大小$k$和命令数量$n$（$1 \leq k \leq 10^4, 1 \leq n \leq 10^5$）。

接下来的$n$行中，每行包含一个方向$d_{i}$和一个距离$a_{i}$（$d_{i}$是$N$、$S$、$W$或$E$；$1 \leq a_{i} \leq 10^9$）。

输出格式

输出被机器人清洁的总面积。

样例$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$

下面是根据题目中的样例，机器人移动过程中访问过的格子被阴影标出。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制	子任务依赖
$1$	$9$	$k=1, n \leq 10, a_{i} \leq 10$
$2$	$10$	$k \leq 10, n \leq 10, a_{i} \leq 100$	$1$
$3$	$11$	$k \leq 1000, n \leq 1000, a_{i}=1$
$4$	$8$	$k \leq 10^4, n \leq 10^5, a_{i}=k$
$5$	$14$	$k=1, n \leq 1000, a_{i} \leq 10^9$	$1$
$6$	$15$	$k \leq 10^4, n \leq 1000, a_{i} \leq 10^9$	$1\sim 3,5$
$7$	$16$	$k=1, n \leq 10^5, a_{i} \leq 10^9$	$1,5$
$8$	$17$	$k \leq 10^4, n \leq 10^5, a_{i} \leq 10^9$	$1\sim 7$