3414 - 扫地机器人

一个扫地机器人正在清洁一个二维坐标平面。扫地机器人是一个边长 k\times k 的正方形,边与坐标轴平行。初始时,扫地机器人左下角位于 (0,0),右上角位于 (k,k)

给定一个由 n 个移动操作组成的序列,第 i 个移动操作由方向 d_iN 表示向上,增加 y 坐标;E 表示向右,增加 x 坐标;W 表示向左,减小 x 坐标;S 表示向下,减小 y 坐标)和距离 a_i(机器人移动的距离)组成。根据给定的机器人移动操作,计算清扫的总面积(被机器人覆盖过的点就算被清扫过的点)。

输入

第一行包含两个整数,机器人的大小 k 和操作数量 n

接下来的 n 行中,每行包含一个移动操作和对应的距离 a_i。移动操作用字母 d_i 表示(N 即向上,E 即向右,W 即向左,S 即向下),且距离 a_i 是一个整数。

输出

输出机器人清扫的总面积。

样例

输入

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

输出

17

输入

3 4
W 2
N 1
W 1
N 2

输出

27

提示


对于 100\% 数据,1 \le k \le 10^41 \le n \le 10^51 \le a_i \le 10^9

时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题