题目描述

《黄金的太阳》独创了一种精灵召唤技能。玩家在冒险中收集精灵，然后就可以在战斗中利用精灵的能量，使用各种召唤技能。

每种召唤技能需要消耗精灵的能量，玩家的精灵能提供的总能量等于 $m$ 点。当释放召唤技能时，根据技能的消耗，需要同等数量的能量，消耗掉的能量不会再恢复。只要有足够的能量，每种技能都可以无限次使用。

玩家目前收集的精灵能够提供的能量等于 $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

提示

使用第 1 个技能 1 次，第 2 个技能 1 次。总伤害量为 12，消耗 5 点能量。总能量为 7，还剩下 2 点能量。

2 3 100
5 30
7 40

-1

2 40 236
651 63
186 62

-1

数据范围

前 20% 数据：$n\le10,m\le30$。

前 50% 数据：$m\le10^4$。

对 100% 数据：$1\le n\le100$，$1\le m\le10^9$，$1\le H\le10^5$，$1\le c_i\le10^9$，$1\le d_i\le10^3$。