题目描述

某座大桥上有 $n_1$ 条从左至右的车道，$n_2$ 条从右至左的车道，还有一条潮汐车道。在早上从左向右行驶的车辆较多，潮汐车道的方向是从左向右；晚上正好相反。 也就是说早上 $n_1+1$ 条左右车道，$n_2$ 条右左车道；晚 上有 $n_1$ 条左右车道，$n_2+1$ 条右左车道。

交通是很复杂的问题，我们有如下的抽象模型： 从早到晚被分为 $m$ 个离散的时刻，编号从 $1$ 开始。 在每个时刻，两侧均有一些车抵达。 设左右车道和右左车道各有 $L,R$ 条车道，那么左侧通行 $L$ 辆车 （即减少 $L$ 辆车），右侧通行 $R$ 辆车。 剩下的车等待下一时刻。 如果在时刻 $m$ 后仍有车辆在等待，那么后面的时刻仍按同样模型进行，只是不会有新到达的车辆了。

你的任务是决定在哪一时刻改变潮汐车道的方向，能使所有车辆等待时间的总和最小化。

不过潮汐车道也不是瞬间就能改变方向的，它需要 $r$ 个时刻来改变方向。也就是说，如果在 $t$ 时刻改变方向，那么在 $[t,t+r-1]$ 时刻内潮汐车道不能使用，即左右和右左车道各有 $n_1$ 和 $n_2$ 条。

输入格式

第一行四个整数 $n_1,n_2,m,r$。

接下来 $m$ 行，第 $i+1$ 行两个整数 $a,b$ 表示在 $i$ 时刻有 $a$ 辆车从左侧抵达，$b$ 辆车从右侧抵达。

输出格式

一行一个整数表示最小总等待时间。

2 2 10 2
1 0
2 1
3 2
4 2
3 3
2 3
1 5
0 3
1 2
0 1

4

数据规模与约定

对于 $100\%$ 的数据，$1\leq n_1,n_2\leq 10$，$1\leq m\leq 10^5$。