该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

保鲜青草

题目描述

黑大帅负责为一只羊准备青草。

为了保证青草的新鲜，每次送来的青草只能保存有限的时间。

在第 $d_i$ 天早晨，黑大帅会向谷仓送来 $b_i$ 捆青草。所有青草的保质期均为 $K$ 天。

具体来说，在第 $d_i$ 天送达的青草，可以在第$d_i,d_i+1,\ldots,d_i+K-1$天食用。

如果到了第 $d_i+K-1$ 天晚餐结束后仍然没有被吃掉，那么剩余的这批青草将全部腐烂，之后不能再食用。

每天按照以下顺序发生事件：

1. 当天早晨，如果有青草送达，则将青草放入谷仓；
2. 到了晚餐时间，如果谷仓中存在尚未腐烂的青草，羊会吃掉恰好 $1$ 捆；
3. 羊总是优先食用最早送达的、仍然可以食用的青草；
4. 晚餐结束后，当天达到保质期的青草全部腐烂。

没有腐烂且没有被吃掉的青草会继续保存在谷仓中。

请计算在第 $1$ 天至第 $T$ 天内，这只羊一共能够吃掉多少捆青草。

输入格式

第一行包含三个整数 $N,T,K$，分别表示：

• 青草的运送次数；
• 统计的天数；
• 每批青草的保质期。

接下来 $N$ 行，每行包含两个整数 $d_i,b_i$，表示：

在第 $d_i$ 天早晨送来 $b_i$ 捆青草。

保证所有运送日期严格递增，即$d_1<d_2<\cdots<d_N$。

输出格式

输出一行一个整数，表示这只羊在前 $T$ 天内一共吃掉了多少捆青草。

样例输入 1

1 5 2
1 3

样例输出 1

2

样例解释 1

第 $1$ 天早晨送来 $3$ 捆青草。

这批青草的保质期为 $2$ 天，因此只能在第 $1$ 天和第 $2$ 天食用。

• 第 $1$ 天吃掉 $1$ 捆；
• 第 $2$ 天吃掉 $1$ 捆；
• 第 $2$ 天晚餐结束后，剩余的 $1$ 捆青草腐烂。

因此前 $5$ 天一共吃掉 $2$ 捆青草。

样例输入 2

2 6 3
1 2
3 3

样例输出 2

5

样例解释 2

第 $1$ 天送来 $2$ 捆青草，可以在第 $1\sim3$ 天食用。

羊在第 $1$ 天和第 $2$ 天分别吃掉一捆，因此第一批青草恰好全部吃完。

第 $3$ 天又送来 $3$ 捆青草，可以在第 $3\sim5$ 天食用。

羊在第 $3,4,5$ 天各吃掉一捆。

因此一共吃掉$2+3=5$捆青草。

样例输入 3

2 6 3
1 5
2 2

样例输出 3

4

样例解释 3

第 $1$ 天送来 $5$ 捆青草，这批青草只能在第 $1\sim3$ 天食用。

第 $2$ 天又送来 $2$ 捆青草，可以在第 $2\sim4$ 天食用。

由于羊总是优先食用最早送达的青草：

• 第 $1$ 天吃第一批青草；
• 第 $2$ 天吃第一批青草；
• 第 $3$ 天吃第一批青草。

第 $3$ 天晚餐后，第一批剩余的 $2$ 捆青草腐烂。

此时第二批还剩 $2$ 捆，但它们只能食用到第 $4$ 天，因此：

• 第 $4$ 天吃掉其中 $1$ 捆；
• 第 $4$ 天晚餐后，剩余 $1$ 捆腐烂。

所以总共吃掉 $4$ 捆青草。

样例输入 4

3 12 4
1 10
5 2
10 5

样例输出 4

9

样例解释 4

第一批青草在第 $1\sim4$ 天有效，虽然共有 $10$ 捆，但最多只能在这 $4$ 天中吃掉 $4$ 捆，其余青草会腐烂。

第二批在第 $5\sim8$ 天有效，共有 $2$ 捆，可以全部吃掉。

第三批在第 $10\sim13$ 天有效，但只统计到第 $12$ 天，因此只能在第 $10,11,12$ 天吃掉 $3$ 捆。

最终答案为$4+2+3=9$。

数据范围与约定

对于所有测试数据，保证：$1\le N\le 2\times10^5$,$1\le T\le 10^{14}$,$1\le K\le 10^{14}$,$1\le d_i\le T$,$1\le b_i\le 10^9$

,$d_1<d_2<\cdots<d_N$

答案保证在 long long 范围内。

• 特殊性质 A：对于所有 $i$，均有 $b_i=1$。
• 特殊性质 B：$K\ge T$。
• 特殊性质 C：对于所有 $i$，均有 $d_{i+1}-d_i\ge K$。