由于各种原因，桐人现在被困在（以下简称）中，而马上 要迎来最终的压力测试——魔界入侵。

唯一一个神一般存在的被消灭了，靠原本的整合骑士的力量 是远远不够的。所以爱丽丝动员了全体人民，与整合骑士一起抗击魔族。

在的驻地可以隐约看见魔族军队的大本营。整合骑士们打算在魔族入侵前 发动一次奇袭，袭击魔族大本营！ 为了降低风险，爱丽丝找到了你，一名优秀斥候，希望你能在奇袭前对魔族大本营进行侦查，并计算出袭击的难度。

经过侦查，你绘制出了魔族大本营的地图，然后发现，魔族大本营是一个的网格图，一共有支军队驻扎在一些网格中（不会有两只军队驻扎在一起）。

在大本营中，每有一个的子网格图包含恰好支军队，我们袭 击的难度就会增加点。

现在请你根据绘制出的地图，告诉爱丽丝这次的袭击行动难度有多大。

第一行，一个正整数，表示网格图的大小以及军队数量。

接下来N行，每行两个整数,,，表示第支军队的坐标。

保证每一行和每一列都恰有一只军队,即每一个和每一个都是不一样 的。

一行，一个整数表示袭击的难度。

5
1 1
3 2
2 4
5 5
4 3

10

显然，分别以和为左上,右下顶点的一个子网格图中有支军队，

这为我们的难度贡献了点。

类似的子网格图在原图中能找出个。

对于的数据，

对于的数据，

对于的数据，

用线段树即可解决

首先，我们发现，如果要满足 的子网格图包含恰好 支军队

那么这 只军队的最大横坐标减去最小横坐标恰好等于这 只军队的最大纵坐标减最小纵坐标

两维不好处理，因此我们把横坐标作为下标，纵坐标作为权值

这样原问题就变成了在一个排列中有多少区间内的数是连续的

我们发现这可以用线段树去维护

我们把线段树的节点定义为以某个点为左端点，以扫到的点为右端点的区间中连续区间的个数

线段树要维护的信息有连续区间个数的最小值，该最小值的个数，以及区间加和操作中的 标记

每次从右边新加入一个点 时，我们把区间 整体加

代表此时又多了一个不连续的区间

此时我们去找 和 的位置，如果它们的位置在 的左边，我们就把 或者 整体减一，代表包含 或者 的区间可以与 合并形成一个大区间

每次枚举一个右端点时就单独计算一下价值