Description

最近xenocide迷上了一款游戏Eufloria，它是这样的，他出生在1号星球，总共有n个星球。出生时带有s个孢子，你可以在一个星球种树，种一棵树要消耗k个孢子，然后每回合这棵树会为你带来1个孢子，一个星球最多种pi棵树。现在游戏要你去征服整个星系，为了方便起见，我们定义所有星球在一条线上，分别编号为1，2...n，且你只能征服了第i星球才能征服第i+1个星球。每个星球都有敌人（当然你出生的1号星球是没有敌人的。。。），消灭这个星球上的所有敌人会消耗掉你ai个孢子。

注：

你一定要消灭掉这个星球上的所有敌人才能在这个星球上种树。

你种树,消灭敌人和把孢子从一个星球转移到另一个星球是不记时间的

现在问你，xenocide最快可以在几个回合内完成游戏

Input

包含多组测试数据 每组数据第一行包含3个正整数n，s，k（n<=100000，s，k<10000） 接下来有有n行每行2个数，分别是ai，pi（0<=ai<10000,0<=pi<=10）

Output

对于每组数据 输出xenocide最快可以在几个回合内完成游戏,如果无法完成游戏就输出-1

Sample

Input

4 1 1
0 10
1000 10
1000 10
0 10

Output

155

Source: xenocide