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

}

## 0 Comments

If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.