Problem: Problem statement

Real variables $ x_1, x_2, ..., x_N $ satisfy the following conditions.

1. $ 0 \ leq x_i \ leq 1 $ ($ 1 \ leq i \ leq N $)
2. $ w_1x_1 + w_2x_2 + ... + w_Nx_N \ leq W $



At this time, find the maximum value that $ v_1x_1 + v_2x_2 + ... + v_Nx_N $ can take. It is known that such a maximum actually exists.

Constraint

* $ 1 \ leq N \ leq 10 ^ 5 $
* $ 1 \ leq W \ leq 10 ^ 5 $
* $ -10 ^ 4 \ leq w_i \ leq 10 ^ 4 $
* $ -10 ^ 4 \ leq v_i \ leq 10 ^ 4 $



input

Input follows the following format. All given numbers are integers.


$ N $ $ W $
$ w_1 $ $ v_1 $
$ w_2 $ $ v_2 $
$ ... $
$ w_N $ $ v_N $

output

Output the maximum possible value of $ v_1x_1 + v_2x_2 + ... + v_Nx_N $ on one line. The output must not have an error greater than $ 10 ^ {-3} $.

Examples

Input

1 1
3 1


Output

0.333333


Input

2 3
3 3
1 2


Output

4.000000


Input

2 1
-1 -3
3 10


Output

3.666667

Solution (in CPP):

Solution:
#include<iostream>
#include<vector>
#include<tuple>
#include<algorithm>

using namespace std;

int main(){
  int N,W;
  cin>>N>>W;
  double cw=0,cv=0;
  vector<tuple<double,double,double> > p,n;
  while(N--){
    long long w,v;
    cin>>w>>v;
    if(w*v>0){
      ((w>0)?p:n).emplace_back(v*1./w,1.*w,1.);
    }else if(v>=0&&w<=0){
      cw+=w;
      cv+=v;
    }
  }
  sort(begin(p),end(p));
  sort(n.rbegin(),n.rend());
  while(!p.empty()){
    double vw=get<0>(p.back());
    double w=get<1>(p.back());
    double &r=get<2>(p.back());
    if(cw+w*r<=W){
      cw+=w*r;
      cv+=vw*w*r;
      p.pop_back();
    }else{
      double l=(W-cw)/w;
      cv+=vw*w*l;
      r-=l;
      break;
    }
  }
  double m=cv;
  while(!p.empty()&&!n.empty()){
    auto &pb=p.back();
    auto &nb=n.back();
    double l=min(get<2>(pb)*get<1>(pb),-get<2>(nb)*get<1>(nb));
    cv+=(get<0>(pb)-get<0>(nb))*l;
    m=max(m,cv);
    get<2>(pb)-=l/get<1>(pb);
    get<2>(nb)-=l/-get<1>(nb);
    ((get<2>(nb)<get<2>(pb))?n:p).pop_back();
  }
  cout<<fixed<<m<<endl;
}