题目描述

⻩⾦的太阳独创了⼀种精灵召唤技能。玩家在冒险中收集精灵，然后就可以在战⽃中利⽤精灵的能量，使⽤各种召

唤技能。

每种召唤技能需要消耗精灵的能量。战⽃开始时，所有精灵都处于可以提供能量的状态。当释放召唤技能时，根据

技能的消耗，需要同等数量的精灵提供能量，提供过能量的精灵，之后就不能再提供能量了。只要有⾜够的精灵提

供能量，每种技能都可以⽆限次使⽤。

例如使⽤消耗为 3 的技能，就需要 3 只精灵提供能量，这 3 只精灵在之后就不能再提供能量了。

玩家⽬前收集了 $m$ 只精灵。有$n$种不同的召唤技能可以使⽤，第$i$种技能的消耗为$c_i$ ，伤害为$d_i$ 。

敌⼈的体⼒为$H$ ，当总伤害⼤于等于$H$时，敌⼈就被击败了。问击败敌⼈时，还剩下的（可以提供能量的）精灵

的最多数量。如果⽆法击败敌⼈，输出$-1$。

输入格式

第 1⾏， 3个正整数$n,m,H$

接下来 $n$ ⾏，每⾏两个正整数$c_i,d_i$

输出格式

输出⼀个整数，击败敌⼈时，还剩下的精灵的最多数量。如果⽆法击败敌⼈，输出$-1$。

3 7 12
3 8
2 4
1 2

2

5 100 200
2 1
4 3
8 9
16 27
32 81

8

2 100000000 100
50000000 4
100000000 9

-1

【说明提示】

样例1说明：

使⽤第 1 个技能 1 次，第 2 个技能 1 次。总伤害量 12，消耗 5 点能量。⼀共有 7 只精灵，其中 5 只提供能量，还

剩下 2 只精灵。

样例2说明：

使⽤第 2 个技能1次，第 3 个技能 1 次，第 4 个技能 1 次，第 5 个技能 2 次。总伤害量 201，消耗 92 点能量。⼀共有 100 只精灵，还剩下 8 只精灵。

提示

$1 \leq n \leq 100,1 \leq m \leq 10^9,1 \leq H \leq 10^5$

$1 \leq c_i \leq 10^9, q \leq d_i \leq 10^3$