旅游

题目限制

1000 ms 256 M

题目描述

小欧参加了一档节目，获得特等奖，可以免费旅游若干个城市。机票住宿全部由主办方承担，但其它的消费就得自己承担了。

他的旅游行程是从第 $x$ 个城市依次旅游到第 $y$ 个城市。但是有时他觉得某些城市没有意思，这样他可以跳过一些城市，主办方承诺机票可以随时改签。但是他不想太早结束他的旅程，所以，他给自己规定，最多跳过 $z$ 个城市，即最远可以从第 $i$ 跳到第 $i+z$ 个城市。

在一个城市游玩总是需要买买买和吃吃吃的。除城市 $x$ 之外，在任何一个城市，小欧都会刚好花掉 $a$ 元，不多不少。有时小欧会格外喜欢某个城市，他可能会在那个城市卖个艺，挣点外快。但即使挣了再多的钱，他也只会花掉 $a$ 元。

现在小欧想知道，经过这一趟旅游，他最多能比出发时多出多少钱。

输入格式

第一行输入5个整数 x,y,z,a,n，其中，n表示他喜欢的城市的数目。（1≤n≤1e5） 之后n行，每行包含两个正整数c[i],m[i]，表示小欧如果在第c[i]个城市卖艺，可以赚m[i]的钱。保证c[i]按递增顺序输入。

输出格式

输出一个整数，表示小欧旅行完以后最多能够比他出发时多出多少钱。答案可以为负。

数据范围

对于20%的数据，$N\le 1000$；

另有30%的数据，$z\le 100$；

对于100%的数据，

$1 \le m[i],a,z \le 10^9$，$1\le n\le 10^5$, $0\le x\le c[i] \le y \le 10^9$。

输入样例

0 10 4 10 2
3 10
8 5

输出样例

-20

样例解释

小欧先跳到点3卖个艺然后跳到点7再跳到点10，他实际去了3个城市花国30元，卖艺挣了10元，这次旅游下来赚国-20元。