PKU 2547 No Tipping

http://poj.org/problem?id=2547
二つの支柱に支えられたある重さの板の上にn個の重りが置かれている。
全ての重りを板が左右に傾くことがないように順番に取り除いていくとき、その取り除き方を答えろというような問題。

適当に取り除けるものがあれば取り除くという貪欲だとサンプルが通らないので、dfsしました。
statusを見て貪欲解がありそうな雰囲気を感じとりましたが、自力じゃわかりませんでした。

PI in[20];
bool vis[1<<20];
PI ans[20];
int n;
bool dfs(int ne,int st,int csum,int cw){
  if(vis[st] || 2*abs(cw)>3*csum)return false;
  if(ne==n)return true;
  vis[st]=true;
  rep(j,n){
    if(st&(1<<j))continue;
    int nw=cw-in[j].F*in[j].S;
    int nsum=csum-in[j].S;
    ans[ne]=in[j];
    if(dfs(ne+1,st|1<<j,nsum,nw))return true;
  }
  return false;
}

main(){
  int l,w;
  int ca=0;
  while(cin>>l>>w>>n,l){
    int sum=w;    
    w=0;
    rep(i,n){
      cin>>in[i].F>>in[i].S;
      w+=in[i].F*in[i].S;
      sum+=in[i].S;
    }
    memset(vis,0,sizeof(vis));
    printf("Case %d:\n",++ca);    
    if(dfs(0,0,sum,w))rep(i,n)cout<<ans[i].F<<' '<<ans[i].S<<endl;
    else cout<<"Impossible"<<endl;
  }
}