007 - 加工機
時間制限 1 秒 / メモリ制限 256 MB / 得点 9 / x 2 /
問題文
アイヅ工業は、加工機でのものづくりの仕事を請け負っています。アイヅ工業が所有する加工機を図1の左に示します。
この加工機は、任意の直方体を加工することができ、その幅、奥行、高さは自由に設定できます。この直方体の上に幅1cmと奥行1cmの刃があります。
この刃は、削りたい位置の真上に動かすことができます。削りたい位置は図1の右に示すような区画の座標で指定します。
図1:加工機の立体図と区画の座標
- 刃を指定した区画の真上に移動します。
- 加工するものに接するまで刃を下ろし、その区画を指定した長さだけ新たに削ります。
- 刃を上げて最初の高さまで戻します。
図2:加工機を用いた切削の例
課題
加工する直方体の大きさと、直方体をどのように削るかを表す情報が与えられたとき、加工後の表面積がいくらになるかを計算するプログラムを作成せよ。
入力
入力は以下の形式で与えられる。
$W \ D \ H \ C$ $x_{1} \ y_{1} \ z{1}$ $x_{2} \ y_{2} \ z{2}$ $\vdots$ $x_{C} \ y_{C} \ z{C}$
1行目に加工する直方体の幅$W\ (1 \leq W \leq 100,000)$、奥行$D\ (1 \leq D \leq 100,000)$、高さ$H\ (1 \leq H \leq 100,000)$、および削る回数$C\ (0 \leq C \leq 100,000)$が与えられる。
続く$C$行に、直方体をどのように削るかを表す情報が与えられる。$x_{i}\ (0 \leq x_{i} \lt W)$と$y_{i}\ (0 \leq y{i} \lt D)$は削る区画の座標を表す。また、$z_{i}\ (1 \leq z_{i} \lt H)$は、その区画を現在の高さからどれだけ削るかを表す整数である。
ただし、各区画について、削った後の高さが1より小さくなるような入力は与えられない。
出力
加工後の表面積を1行に出力する。
入出力例
入力例1
3 4 5 2 0 0 4 1 1 4
出力例1
110
入力例2
1 2 3 0
出力例2
22
入力例2は、一度も削らない場合なので、表面積は与えられた直方体の表面積と同じになる。