U187659 【D&S R1-3】无敌贾维提桶跑路

♫啊朋友再见♫ 注意：空间被开大了。 #### ~~数据重造完成。~~ 又炸了，请酌情提交。

现在有 $N$ 个地点编号为 $1$ 至 $N$。贾维一行开车从 $1$ 出发前往 $N$。车有一个油箱大小 $K$，出发时油箱是满的。贾维一行有一个钱数变量 $c$，由于出发时过于匆忙所以出发时没有钱。钱没有上限。 贾维一行有两种移动方式（设当前在地点 $x$）： - 奥斯塔的安全驾车：消耗 $1$ 点油量，花费 $1$ 单位时间，从 $x$ 移动到 $x-1$ 或 $x+1$。 - 布洛卡的快速推车：花费 $3$ 个单位时间，从 $x$ 移动到 $x-1$ 或 $x+1$。 这条路上还有两种地点，分别是： - 散装的 CE6，共计 $p$ 个：有两个属性 $x,y$。表示在 $x$ 这个地点花费 $y$ 个单位时间可以得到 $1$ 个单位的钱。 - 叙拉古油业加油站，共计 $q$ 个：有两个属性 $u,v$，表示在 $u$ 这个地点花费 $v$ 个单位的钱可以直接把油箱加满，不花费时间。 保证一个地点最多只有一个加油站或 CE6 且加油站和 CE6 不会同时出现在一个地点。 计算最小花费时间。

第一行有四个整数 $N,K,p,q$。 接下来 $p$ 行每行两个整数 $x,y$，含义见上。 接下来 $q$ 行每行两个整数 $u,v$，含义见上。

输出一行，贾维一行到达 $N$ 的最小时间。

【样例解释】 第一组样例中贾维一行开 $5$ 个单位的车再推 $4$ 个单位的车，总时间为 $17$。 第二组样例中贾维一行先开车打完 CE6，再开车兼推车地到达加油站，最后开车前往 $N$，总时间为 $45$。 --- 【数据范围与提示】 #### 本题采用捆绑测试。 | Subtask 编号 | $n$ | $K$ | $p,q$ | $y$ | $v$ | 分数 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $\leq 100$ | $\leq 100$ | $\leq 20$ |$\leq 100$ | $\leq 5$ | $15$ | | $2$ | $\leq 10^4$ | $\leq 100$ | $\leq 100$ | $\leq 100$ | $\leq 5$ | $15$ | | $3$ | $\leq 10^6$ | $\leq 10^6$ | $\leq 10^3$ | $\leq 10^6$ | $\leq 10^6$ | $30$ | | $4$ | $\leq 10^6$ | $\leq 10^6$ | $\leq 3\times 10^3$ | $\leq 10^6$ | $\leq 10^6$ | $40$ | 对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$0\leq K\leq 10^6$，$0\leq p, q\leq 3\times 10^3$，$1\leq x,u\leq n $，$0\leq y,v\leq 10^6$。