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;

}