Background

Translated from ROIR 2023 D1T3。

A cleaning robot is cleaning a 2D coordinate plane. The cleaning robot is a square of side length $k\times k$, with its sides 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

You are given a sequence of $n$ move operations. The $i$-th move operation consists of a direction $d_i$ (N means up, increasing the $y$ coordinate; E means right, increasing the $x$ coordinate; W means left, decreasing the $x$ coordinate; S means down, decreasing the $y$ coordinate) and a distance $a_i$ (the distance the robot moves). Based on the given robot moves, compute the total cleaned area (a point is considered cleaned if it has been covered by the robot at least once).

Input Format

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

In the next $n$ lines, each line contains one move operation and the corresponding distance $a_i$. The move operation is given by a 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.

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

17

3 4
W 2
N 1
W 1
N 2

27

Hint

Sample explanation: The figure below shows the robot movements in the two samples.

Constraints

This problem uses bundled testdata.

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

Translated by ChatGPT 5