You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

我们来看一个坐标平面，计划使用机器人吸尘器进行清洁。机器人吸尘器是一个大小为 $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 5
E 2
N 2
W 4
S 4
E 4

17

3 4
W 2
N 1
W 1
N 2

27

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

数据范围与提示

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