Problem Background

Translated from ROIR 2023 D1T3.

A cleaning robot is operating on a two-dimensional coordinate plane. The robot is a square with side length $k \times k$ and its sides are parallel to the coordinate axes. Initially, the bottom-left corner of the robot is at $(0,0)$ and the top-right corner is at $(k,k)$.

Problem Description

Given a sequence of $n$ movement operations, the $i$-th movement operation consists of a direction $d_i$ (N for moving up, increasing the $y$ coordinate; E for moving right, increasing the $x$ coordinate; W for moving left, decreasing the $x$ coordinate; S for moving down, decreasing the $y$ coordinate) and a distance $a_i$ (the distance the robot moves). Calculate the total area cleaned (a point is considered cleaned if it has been covered by the robot).

Input Format

The first line contains two integers, the size of the robot $k$ and the number of operations $n$.

The next $n$ lines each contain a movement operation and the corresponding distance $a_i$. The movement operation is represented by the letter $d_i$ (N for up, E for right, W for left, S for down), and the distance $a_i$ is an integer.

Output Format

Output the total area cleaned by the robot.

Sample Input and Output

Sample Input #1

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

Sample Output #1

17

Sample Input #2

3 4
W 2
N 1
W 1
N 2

Sample Output #2

27

Notes

The following diagrams illustrate the movement of the robot in the two samples.

This problem uses bundled tests.

For $100\%$ of the data, $1 \le k \le 10^4$, $1 \le n \le 10^5$, $1 \le a_i \le 10^9$.

Note: The robot may revisit areas it has already covered.

见题面 Input 部分

见题面 Output 部分