#include<stdio.h>
int main(){
int c;
scanf("%d",&c);
while(c--){
int mm,i,j,min=9999999,p[40000],m[40000],maxp=0,maxm=0;
short a[500],b[500],minus[500];
scanf("%d",&mm);
for(i=0;i scanf("%d %d",&a[i],&b[i]);
minus[i]=a[i]-b[i];
if(minus[i]==0 && min>minus[i]) min=minus[i];
if(minus[i]>0 && maxp if(minus[i]<0 && maxm>minus[i]) maxm=minus[i];
}
if(maxp*maxm==0&&min==9999999){
printf("IMPOSSIBLE");
goto next;
}

p[0]=0;
    m[0]=0;
    for(i=1;i<=-1*maxp*maxm;i++){
        p[i]=9999999;
        for(j=0;j<mm;j++){
            if(minus[j]>0){
                if(minus[j]<=i){
                    if(p[i]>p[i-minus[j]]+a[j])
                    p[i]=p[i-minus[j]]+a[j];
                }
            }
        }
    }
    for(i=1;i<=-1*maxp*maxm;i++){
        m[i]=9999999;
        for(j=0;j<mm;j++){
            if(minus[j]<0){
                if(-minus[j]<=i){
                    if(m[i]>m[i+minus[j]]+a[j])
                    m[i]=m[i+minus[j]]+a[j];
                }
            }
        }
    }
    for(i=0;i<=-1*maxp*maxm;i++){
        if(min>p[i]+m[i]&&m[i]!=0&&p[i]!=0)
            min=p[i]+m[i];
    }
    printf("%d\n",min);

next:
    0;
}
return 0;

}
일단 저의 소스입니다.
시간복잡도가 아마 O(200^2*500) 인가 나올건데 TLE가 뜨네요.
어떻게 하면 최적화 할수 있는지 조언 부탁드립니다.