题目描述

训练场是一条从左到右的直线，起点在位置 $0$。线上有 $n$ 个训练点，第 $i$ 个训练点距离起点 $x_i$，到达它可以获得分数 $s_i$，分数可能为负。保证输入的 $x_i$ 递增。

训练机器人原本每次只能向右移动恰好 $d$ 的距离。若花费 $g$ 个调试点数升级机器人，则它每次可以选择向右移动的距离范围为：

• 当 $g<d$ 时，距离可以是 $d-g,d-g+1,\ldots,d+g$；
• 当 $g\ge d$ 时，距离可以是 $1,2,\ldots,d+g$。

机器人可以从起点出发，多次向右移动并停在某些训练点上，获得经过训练点的分数之和，也可以在任意时刻结束。请问至少需要花费多少调试点数，才能使总分达到至少 $k$。如果无论如何都无法达到 $k$，输出 $-1$。

输入格式

第一行包含三个正整数 $n,d,k$，分别表示训练点数量、原始移动距离和目标分数。

接下来 $n$ 行，每行包含两个整数 $x_i,s_i$，表示第 $i$ 个训练点的位置和分数。保证 $x_i$ 递增。

输出格式

输出一行一个整数，表示最少需要花费的调试点数；若无法达到目标，输出 $-1$。

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

2

7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

-1

样例说明

第一组样例中，花费 $2$ 后可以依次到达位置 $2,5,10,13,17,20$，得到的总分为 $15$，不少于 $10$。

第二组样例中，所有可选路线的最高总分也达不到 $20$。

数据范围

本题共 $10$ 组测试数据，每组等分。

对于全部数据，$1\le n\le 5\times10^5$，$1\le d\le 2\times10^3$，$1\le x_i,k\le 10^9$，$|s_i|<10^5$。

对于第 $1,2$ 组测试数据，保证 $n\le 10$。

对于第 $3,4,5$ 组测试数据，保证 $n\le 500$。

对于第 $6,7,8$ 组测试数据，保证 $d=1$。