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 <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

#define rep(i,n) for(int i=0; i<(int)n; ++i)

int main() {
    int n,W;
    cin>>n>>W;

    double ans = 0,weight = 0.0;
    vector<double> w(n), v(n);
    rep(i,n) cin>>w[i]>>v[i];

    vector<pair<double,int> > pv;
    rep(i,n) {
        if(w[i] >= 0 && v[i] <= 0) continue;
        if(w[i] <= 0 && v[i] >= 0) {
            ans += v[i], weight += w[i];
            continue;
        }

        if(v[i] >= 0) {
            ans += v[i], weight += w[i];
            w[i] *= -1, v[i] *= -1;
        }
        pv.push_back(make_pair(v[i]/w[i],i));
    }

    sort(pv.begin(), pv.end());
    //reverse(pv.begin(), pv.end());

    rep(i,pv.size()) {
        if(weight <= W) break;
        int idx = pv[i].second;

        if(weight+w[idx] >= W) {
            weight += w[idx];
            ans += v[idx];
        }else{
            ans += v[idx]*(W-weight)/w[idx];
            weight = W;
        }
    }

    printf("%.12f\n", ans);
}