1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 int a[105],b[105];
 6 int dp[105][105];    //代表到第 i 秒剩余 j 魔法值打掉BOSS的HP 
 7 int main()
 8 {
 9     int n,t,q;
10     while(cin>>n>>t>>q){
11         if(n==0 && t==0 && q==0)
12             break;
13         for(int i=1;i<=n;i++)
14             cin>>a[i]>>b[i];
15         //freopen("output.txt","w",stdout);
16         memset(dp,-1,sizeof(dp));
17         dp[0][100]=0;    //刚开始的时候出了MP=100，其余都为无效
18         int T;
19         if(100%q==0)
20             T=100/q;
21         else
22             T=100/q+1;
23         int i,j,k;
24         for(i=1;i<=T;i++){    //最多到100秒
25             for(j=0;j<=100;j++){    //一次遍历dp[i-1][0..100]的所有情况 
26                 if(dp[i-1][j]==-1)
27                     continue;
28                 for(k=1;k<=n;k++){    //使用技能攻击 
29                     if(j-a[k]<0)     //如果剩余的MP不足以使用这个技能，则跳出本次循环 
30                         continue;
31                     int temp;
32                     temp=j-a[k]+t>100?100:j-a[k]+t;
33                     if(dp[i][temp]==-1){    //没到达过这个MP 
34                         dp[i][temp]=dp[i-1][j]+b[k]; 
35                         if(dp[i][temp]>=100)
36                             goto label;
37                     }
38                     else{    //说明之前有降到过这个MP，这个时候比较哪一个伤害高，记录伤害高的值 
39                         if(dp[i-1][j]+b[k] > dp[i][temp]){    //如果当前技能伤害高
40                             dp[i][temp]=dp[i-1][j]+b[k]; 
41                             if(dp[i][temp]>=100)
42                                 goto label;
43                         }
44                     }
45                 }
46                 if(j+t>=100){    //用普通攻击
47                     if(dp[i-1][j]+1 > dp[i][100]) {
48                         dp[i][100] = dp[i-1][j]+1;
49                         if(dp[i][100]>=100)
50                             goto label;
51                     }
52                 }
53                 else{
54                     if(dp[i-1][j]+1 > dp[i][j+t]){
55                         dp[i][j+t]=dp[i-1][j]+1;
56                         if(dp[i][j+t]>=100)
57                             goto label;
58                     }
59                 }
60             }
61         }
62         label:
63         if(i>T)    //正常退出，代表在规定时间内没打死BOSS，你挂了 
64             cout<<"My god"<<endl;
65         else
66             cout<<i<<endl;
67     }
68     return 0;
69 }