1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#include<algorithm>
#define N 20005
using namespace std;
int f[N],T[N],n,m,A,B,i,j,k,L;
int main(){
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++){
        scanf("%d%d",&A,&B);T[L=1]=B;
        for (L=2;;L++)
            if ((T[L]=T[L-1]+(int)((T[L-1]-T[L-2])*1.07))>m) break;L--;
        for (j=m;j;j--)
            for (k=1;T[k]<=j&&k<=L;k++)
                f[j]=max(f[j],f[j-T[k]]+k*A);
  }printf("%d\n",f[m]);
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX