Allowance

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1842		Accepted: 763

Description

As a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).Using the given set of coins, he would like to pay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week.Please help him ompute the maximum number of weeks he can pay Bessie.

Input

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.

Output

* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowance

Sample Input

3 610 11 1005 120

Sample Output

111

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 struct TT 7 { 8     int  v,w; 9 }a[25];10 int need[25];11 bool cmp(TT m, TT n)12 {13   if(m.v>n.v) return true;14          return false;15 }16 int main()17 {18     int n,i,k;19     int value,aa,bb,ans;20     while(~scanf("%d %d",&n,&value))21     {22         ans = 0;23         k = 0;24         for( i=0;i
         
          = value)28             {29                  ans = ans+bb;30             }31             else32              {33                  a[k].v = aa;34                  a[k].w = bb;35                  k++;36              }37         }38         //k = n;39         //printf("sdfgsdf\n");40         sort(a,a+k,cmp);41         while(1)42         {43             memset(need,0,sizeof(need));44             int sum = value;45             for(int i=0; i
          
           0)52 {53 for(int i=k-1;i>=0;i--)54 {55 if(a[i].w && a[i].v>=sum)56 {57 need[i]++;58 sum = 0;59 break;60 }61 }62 }63 if(sum>0) break;64 int s = 0x3f3f3f3f;65 for(int i=0;i