問題文
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 为 Niwango 君建造了一座新的无线电塔。 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