TRANSPORTING CARGO V2

 

TRANSPORTING CARGO V2



A particular vehicle has two compartments that store cargo. One on the left, and one on the right. The vehicle is being used to transport NN indivisible objects. The ii-th object weighs wiwi and occupies vivi volume. Both compartments have a maximum capacity VV. Neither compartment can contain items if the sum of their volumes exceeds VV. You have to place each object in either the left or the right compartment.


A difference in total weights in the two compartments ruins the balance of the vehicle. Place the objects in a manner such that the difference in the sum of weights of the two compartments is minimized. Output −1−1 if it is not possible to fit the objects in the two compartments.

Input


Two integers N,VN,V in that order.


NN lines follow. Two integers wi,viwi,vi on the (i+1)(i+1)-th line.

Constraints


1≤N≤301≤N≤30


1≤vi≤V≤2001≤vi≤V≤200


1≤∑wi≤5⋅1031≤∑wi≤5⋅103

Output


A single integer denoting the minimum possible difference of weight between the two compartments. Output −1−1 if it is not possible to fit the objects in the two compartments.

Example 1


Input
5 10
16 2
19 2
16 3
15 3
19 4



Output
9

int ans=INT_MAX;
void helper(int i,int v,vector<int>&wt,vector<int>&vol,int v1,int v2,int w1,int w2){
  
  if(i==wt.size()){
    ans=min(ans,abs(w1-w2));
    return;
  }
  if(v1+vol[i]<=v){
    helper(i+1,v,wt,vol,v1+vol[i],v2,w1+wt[i],w2);
  }
  if(v2+vol[i]<=v){
    helper(i+1,v,wt,vol,v1,v2+vol[i],w1,w2+wt[i]);
  }
  if(ans==0)return;
}


void solve() {

int n,v;
cin>>n>>v;

vi weight(n),volume(n);
for (int i = 0; i < n; i++)
{
  cin>>weight[i]>>volume[i];
}
helper(0,v,weight,volume,0,0,0,0);
if(ans==INT_MAX){
  cout<<-1<<endl;
  return;
}
cout<<ans<<endl;
}


Post a Comment

0 Comments