seuOJ183 - 飞扬的小鸟

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编：

游戏界面是一个长为 $n$ ，高为 $m$ 的二维平面，其中有 $k$ 个管道(忽略管道的宽度)，管道中间留有的缝隙始终为 $1$ 。小鸟可看作 $1 \times 1$ 的正方形。
小鸟始终在游戏姐面内移动。小鸟从游戏姐面最左边高度为 $l$ 的地方出发，到达游戏姐面最右边时，游戏完成。
小鸟每个单位时间沿横坐标方向右移距离为 $1$ ，竖直移动的距离由玩家控制。有两个按钮，按下第一个按钮小鸟上升高度 $1$ ，按下第二个按钮小鸟下降高度 $1$ 。每个单位时间可以任意点击按钮，效果叠加。如果不按，小鸟高度不变。
小鸟高度等于 $0$ 或者小鸟碰到管道时，游戏失败。小鸟高度为 $m$ 时，无法再上升。

kimoyami 最近迷上了这个游戏，但他发现他分数一直不高。他决定开挂对管道进行修改。他可以在游戏开始前修改管道之间的空隙的位置。具体的操作是，选择一个管道，用两个按钮进行修改，按下第一个管道缝隙上升 $1$ ，按下第二个按钮管道缝隙下降 $1$ 。管道的缝隙并不能变大，只能位置发生变化。

kimoyami 想知道他通关至少要按多少次按钮(包括修改管道按下的按钮的次数)。

第一行三个整数 $n,\ m,\ k(1 \leq n,\ m \leq 10^9,\ 1 \leq k \leq 10^6)$ 。

接下来 $k$ 行，每行两个整数 $x_i,\ y_i(1 \leq x_i \leq n,\ 1 \leq y_i \leq m)$ ，表示管道空隙的位置，保证 $x_i$ 单调递增。

接下来一行一个整数 $l(1 \leq l \leq n)$ ，表示小鸟开始的高度。

一行一个整数 $s$ ，表示最少按下按钮的次数。

如图，没有修改管道，游戏时第一个按钮按了4次。