/ 
Time Limit: 2.525 sec / Memory Limit: 246 MB
問題文
dwango社は電波塔を N 基持っており、すべての電波塔は一直線上に並んでいます。 この直線を数直線とみなしたとき、 i 番目の電波塔は座標 x_i にあり、高さは h_i です。諸事情により、x_i, h_i はすべて正の偶数です。 また、任意の i≠j に対し、 x_i≠x_j,h_i≠h_j を満たします。
各電波塔は、自分より座標が大きく、かつ高さも高いような電波塔のみに情報を送ることができます。
ニワンゴくんはより多くの電波塔を経由して届いた情報が好きです。 そのため、整数列 a_1,a_2,...,a_t であって、 x_{a_k} < x_{a_{k+1}} かつ h_{a_k} < h_{a_{k+1}} がすべての 1 ≦ k ≦ t-1 で成り立つようなもののうちの最大の長さと等しい嬉しさを得ます。
dwango社はニワンゴくんのために、新しく電波塔を 1 基作ってあげることにしました。諸事情により、その電波塔のある座標と電波塔の高さはともに正の奇数でなければなりません。
ニワンゴくんの嬉しさが増加するように電波塔を作るとき、その (座標, 高さ) の組としてありうるものはいくつあるか答えてください。
なお、座標が W より大きい場所と、高さが H より高い場所には強力な磁気嵐が発生しているので電波塔はなく、また新しく作ることもできません。
入力
入力は以下の形式で標準入力から与えられる。
N W H x_1 h_1 . . . x_N h_N
- 1 行目には、整数 N(1 ≦ N ≦ 252525) と W(4 ≦ W ≦ 10^9, Wは偶数) と H(4 ≦ H ≦ 10^9, Hは偶数) が空白を区切りとして与えられる。
- 続く N 行には、 i 番目の電波塔の座標と高さを表す整数 x_i(2 ≦ x_i ≦ W-2, x_iは偶数) と h_i(2 ≦ h_i ≦ H-2, h_iは偶数) が空白を区切りとして与えられる。
- すべての i(1 ≦ i ≦ N-1) について、 x_i < x_{i+1} を満たす。また、 i ≠ j なら h_i ≠ h_j を満たす。
部分点
この問題には部分点が設定されている。
- N ≦ 52 を満たすデータセットに正解した場合、部分点として 20 点が与えられる。
- N ≦ 2525 を満たすデータセットにも正解した場合、部分点として追加で 20 点が与えられる。
- すべてのデータセットに正解した場合、追加で 80 点が与えられ、合計で 120 点となる。
出力
ニワンゴくんの嬉しさを増加させるような新しい電波塔の位置の (座標, 高さ) の組としてありうるものの個数を表す整数を 1 行に出力せよ。 出力が 32 ビット符号付き整数の範囲に収まらない可能性があることに注意すること。
出力の最後には改行を忘れないこと。
入力例1
2 6 6 2 4 4 2
出力例1
6
(座標,高さ) の組としてありうるものは、 (1,1),(1,3),(3,1),(3,5),(5,3),(5,5) の 6 つです。
入力例2
4 10 12 2 6 4 2 6 10 8 4
出力例2
16
入力例3
4 10 10 2 6 4 8 6 2 8 4
出力例3
12
入力例4
5 252525252 555255252 25252 52525252 22225252 2225252 55252252 552222222 252522222 52 252525222 555222222
出力例4
7475142133811101