题目描述

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

每种召唤技能需要消耗精灵的能量。战⽃开始时，所有精灵都处于可以提供能量的状态。当释放召唤技能时，根据 技能的消耗，需要同等数量的精灵提供能量，提供过能量的精灵，之后就不能再提供能量了。只要有⾜够的精灵提 供能量，每种技能都可以⽆限次使⽤。

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

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

敌⼈的体⼒为H，当总伤害⼤于等于H时，敌⼈就被击败了。问击败敌⼈时，还剩下的（可以提供能量的）精灵 的最多数量。如果⽆法击败敌⼈，输出-1。

输入格式

第1⾏， 3个正整数n,m.H 接下来n⾏，每⾏两个正整数ci,di

输出格式

输出⼀个整数，击败敌⼈时，还剩下的精灵的最多数量。如果⽆法击败敌⼈，输出-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 只精灵。

数据规模与约定

对于 $20\%$ 的数据，$n \le 10$ ， $m \le 30$。 对于 $50\%$ 的数据，$m \le 10^4$。 对于 $100\%$ 的数据，$n \le 100$ ，$m \le 10^9$, $1\le H \le 10^5$。。