题目描述

在一个无限大的坐标平面上，需要使用机器人吸尘器进行清扫。

机器人吸尘器是一个边长为 $k$ 的正方形，边与坐标轴平行。初始时，机器人的左下角位于点 $(0,0)$，右上角位于点 $(k,k)$。

给定机器人接下来执行的 $n$ 条移动命令。第 $i$ 条命令由方向 $d_i$ 和距离 $a_i$ 描述，其中：

• N 表示向上移动，即 $Y$ 坐标增加；
• S 表示向下移动，即 $Y$ 坐标减少；
• W 表示向左移动，即 $X$ 坐标减少；
• E 表示向右移动，即 $X$ 坐标增加。

机器人在任意时刻都会清扫其正方形覆盖的全部区域。也就是说，一个点被清扫，当且仅当它在某个时刻属于机器人所在的 $k\times k$ 正方形区域。

请根据给定的移动命令，计算机器人清扫过的区域总面积。

输入格式

第一行包含两个整数 $k,n$，分别表示机器人边长和命令数量。

接下来 $n$ 行，每行包含一个字符 $d_i$ 和一个整数 $a_i$，表示第 $i$ 次移动的方向和距离。

输出格式

输出一个整数，表示机器人清扫过的区域总面积。

数据范围

$$1\le k\le 10^4,$$ $$1\le n\le 10^5,$$ $$d_i\in \{\texttt{N},\texttt{S},\texttt{W},\texttt{E}\},$$$$1\le a_i\le 10^9.$$

答案保证可以用 64 位有符号整数存储。

子任务

子任务	分值	附加限制	依赖子任务
1	9	$k=1,n\le 10,a_i\le 10$	无
2	10	$k\le 10,n\le 10,a_i\le 100$	1
3	11	$k\le 1000,n\le 1000,a_i=1$	无
4	8	$k\le 10^4,n\le 10^5,a_i=k$
5	14	$k=1,n\le 1000,a_i\le 10^9$	1
6	15	$k\le 10^4,n\le 1000,a_i\le 10^9$	1-3,5
7	16	$k=1,n\le 10^5,a_i\le 10^9$	1,5
8	17	$k\le 10^4,n\le 10^5,a_i\le 10^9$	1-7

样例输入 1

1 5
E 2
N 2
W 4
S 4
E 4

样例输出 1

17

样例输入 2

3 4
W 2
N 1
W 1
N 2

样例输出 2

27