# 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;
}