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 <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define INF 100000000
#define MOD 1000000007
#define EPS 1e-10
#define MAX_N 10000
using namespace std;
typedef long long ll;
typedef pair<int,bool> P;
typedef pair<P,P> PP;

int N;
double W;
double w[100000], v[100000];
double ans = 0.0, now;
struct Q{
    double r, w, v;
    bool operator<( const Q& right) const {
        return r < right.r;
    }
    bool operator>( const Q& right) const {
        return r > right.r;
    }
};
vector<Q> p, m;
int ip, im;

int main(){
    cin >> N >> W;
    rep(i,N){
        cin >> w[i] >> v[i];
        if(w[i] <= 0.0){
            if(v[i] >= 0.0){
                W -= w[i];
                ans += v[i];
            } else{
                if(w[i] < 0.0){
                    Q tmp;
                    tmp.r = -1.0*v[i]/w[i];
                    tmp.w = -1*w[i]; tmp.v = -1*v[i];
                    m.push_back(tmp);
                }
            }
        } else{
            if(v[i] > 0){
                Q tmp;
                tmp.r = v[i]/w[i];
                tmp.w = w[i]; tmp.v = v[i];
                p.push_back(tmp);
            }
        }
    }
    sort(m.begin(),m.end(),greater<Q>());
    sort(p.begin(),p.end(),greater<Q>());
    while(ip < p.size()){
        if(p[ip].w >= W){
            ans += (W/p[ip].w)*p[ip].v;
            p[ip].v *= (1.0-W/p[ip].w);
            p[ip].w -= W;
            break;
        } else{
            ans += p[ip].v;
            W -= p[ip].w;
            ip++;
        }
    }
    now = ans;
    while(ip != p.size() && im != m.size()){
        if(p[ip].w >= m[im].w){
            now += p[ip].v*(m[im].w/p[ip].w);
            now -= m[im].v;
            p[ip].v *= (1.0-m[im].w/p[ip].w);
            p[ip].w -= m[im].w;
            im++;
        } else{
            now += p[ip].v;
            now -= m[im].v*(p[ip].w/m[im].w);
            m[im].v *= (1.0-p[ip].w/m[im].w);
            m[im].w -= p[ip].w;
            ip++;
        }
        ans = max(ans,now);
    }
    printf("%.9f\n",ans);
}