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 <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

const double EPS=(1e-10);
typedef long long ll;
bool EQ(double a,double b){
  return abs((a)-(b))<EPS;
}
int N;
double W;
double wi[100001];
double vi[100001];
double xi[100001];

typedef pair<double,int> pdi;

void solve(){
    cin>>N>>W;
    for(int i=0;i<N;i++)cin>>wi[i]>>vi[i];
    for(int i=0;i<N;i++)xi[i]=1;
    priority_queue<pdi> grt;
    priority_queue<pdi> dec;
    double maxVal=0;
    for(int i=0;i<N;i++){
        if((wi[i]<0||EQ(wi[i],0))&&(vi[i]>0||EQ(vi[i],0))){
            xi[i]=0;
            maxVal+=vi[i];
            W+=(-wi[i]);
        }
        else if((wi[i]>0||EQ(wi[i],0))&&(vi[i]<0||EQ(vi[i],0)))xi[i]=0;
        else{
            if(wi[i]<0&&vi[i]<0){
                wi[i]*=-1;
                vi[i]*=-1;
                dec.push(pdi(wi[i]/vi[i],i));
            }
            else if(wi[i]>0&&vi[i]>0)grt.push(pdi(vi[i]/wi[i],i));
        }
    }
    while(grt.size()){
        pdi p=grt.top();grt.pop();
        if(wi[p.second]*xi[p.second]<W||EQ(wi[p.second]*xi[p.second],W)){
            W-=wi[p.second]*xi[p.second];
            maxVal+=vi[p.second]*xi[p.second];
            xi[p.second]=0;
        }
        else{
            double quan=W/(wi[p.second]);
            if(!EQ(quan,0)){
                maxVal+=vi[p.second]*quan;
                xi[p.second]-=quan;;
                grt.push(p);
                W=0;
            }
            else{
                double needW=xi[p.second]*wi[p.second];
                double curFullVal=xi[p.second]*vi[p.second];
                double curGetW=0;
                double curGetVal=0;
                while(dec.size()){
                    pdi pp=dec.top();dec.pop();
                    if(!EQ(p.first,(1.0/pp.first))&&(p.first<1.0/pp.first))break;
                    if(EQ(curGetW+wi[pp.second]*xi[pp.second],needW)||curGetW+wi[pp.second]*xi[pp.second]>needW){
                        double curQuan=(needW-curGetW)/wi[pp.second];
                        curGetW+=curQuan*wi[pp.second];
                        curGetVal+=curQuan*vi[pp.second];
                        xi[pp.second]-=curQuan;
                        if(!EQ(1,xi[pp.second]))dec.push(pp);
                        break;
                    }
                    else{
                        curGetW+=wi[pp.second]*xi[pp.second];
                        curGetVal+=vi[pp.second]*xi[pp.second];
                    }
                }
                if(EQ(curGetW,needW)){
                    if(EQ(curGetVal,curFullVal)||curGetVal<curFullVal)maxVal+=curFullVal-curGetVal;
                    else break;
                }
                else{
                    if(curGetVal<curFullVal*(curGetW/needW)||EQ(curGetVal,curFullVal*(curGetW/needW)))
                        maxVal+=(-curGetVal+curFullVal*(curGetW/needW));
                    break;
                }
            }
        }
    }
    printf("%.10f\n",maxVal);
}
int main(){
    solve();

    return 0;
}