縄張り(Territory)

あなたは南北方向にとても長く伸びたたくさんの道路と,東西方向にとても長く伸びたたくさんの道路が交わった形をした街に住んでいる.隣り合う2 つの南北方向の道路の間隔は 1 km である.また,隣り合う 2 つの東西方向の道路の間隔も 1 km である.

この街には市役所が 1 つある.市役所のある交差点を $(0,0)$ と表す.この街の交差点は 2 つの整数 $i, j$ を用いて交差点 $(i, j)$ と表される.すなわち,交差点 $(i, j)$ とは,交差点 $(0,0)$ から東に $i$ km ($i < 0$ のときは西に $-i$ km),北に $j$ km ( $j < 0$ のときは南に $-j$ km) 進んだ位置の交差点を表す.

市役所ではジョイ君という名の 1 匹の犬を飼っている.ジョイ君は $K$ 日間の散歩の計画を立てた.散歩の計画は以下の通りである.

市役所では $K$ 日間の散歩によってできるジョイ君の縄張りについて話題になっている.4 つの交差点 $(a,b),(a + 1,b),(a + 1,b + 1),(a,b + 1)$ のいずれにもジョイ君が 1 回以上印を付けているとき,4 つの交差点で囲まれた区画はジョイ君の縄張りに属する.

あなたは,ジョイ君の散歩計画から,ジョイ君の縄張りに属する区画の個数を計算するプログラムを作成することとなった.

この街の道路はとても長く,また,南北方向にも東西方向にも十分たくさんの道路があるため,散歩の途中でジョイ君が道路の端や街の端に到達することはない.

課題

ジョイ君の散歩計画が与えられると,ジョイ君の縄張りに属する区画の個数を求めるプログラムを作成せよ.

入力

標準入力から以下の入力を読み込め.

出力

標準出力に,ジョイ君の縄張りに属する区画の個数を 1 行で出力せよ.

制限

すべての入力データは以下の条件を満たす.

入出力例

入力例1

12 1
EENWSEEESWWS

出力例1

3

この入力例では,散歩は 1 日間で行われる.1 日目にジョイ君は市役所から出発して下図のように移動する.黒丸はジョイ君が印を付けた交差点,白丸はジョイ君が印を付けていない交差点,二重丸は市役所のある交差点,数字は各ステップを表す.


ジョイ君の移動経路

入力例 1 において,下図の斜線部分で示された 3 個の区画がジョイ君の縄張りに属する.


入力例1 におけるジョイ君の縄張り

入力例2

12 2
EENWSEEESWWS

出力例2

7

入力例 2 では,散歩が 2 日間に渡り行われる.それぞれの日の移動経路は入力例 1 と同一である.散歩が完了したとき,下図の斜線部分で示された 7 個の区画がジョイ君の縄張りに属する.


入力例2 におけるジョイ君の縄張り

入力例3

7 1
ENNWNNE

出力例3

0

入力例 3 では,ジョイ君の縄張りに属する区画は存在しない.

入力例4

16 5
WSESSSWWWEEENNNW

出力例4

21

クリエイティブ・コモンズ・ライセンス

第15回 日本情報オリンピック本選 課題   2016 年 2 月 14 日