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

struct State{
	int w, v;
	double cost;
	State(int w_, int v_){
		w = w_; v = v_; cost = (double)v_ / w_;
	}
	State(){}
};
bool operator<(const State& a, const State& b){
	return a.cost < b.cost;
}

int main(){
	int N, W;
	scanf("%d %d", &N, &W);
	
	double weight=0, value=0;
	vector<State> a;
	for(int i=0 ; i < N ; i++ ){
		int w_, v_;
		scanf("%d %d", &w_, &v_);
		if( w_ <= 0 && v_ >= 0 ){
			weight += w_;
			value += v_;
			continue;
		}else if( w_ >= 0 && v_ <= 0 ){
			continue;
		}else if( w_ <= 0 && v_ <= 0 ){
			weight += w_;
			value += v_;
			w_ *= -1;
			v_ *= -1;
		}
		a.push_back( State(w_, v_) );
	}
	sort(a.rbegin(), a.rend());
	N = a.size();
	for(int i=0 ; i < N ; i++ ){
		if( weight + a[i].w < W ){
			weight += a[i].w;
			value += a[i].v;
		}else{
			double x = (double)(W - weight) / a[i].w;
			weight += a[i].w * x;
			value += a[i].v * x;
			break;
		}
	}
	printf("%.8f\n", value);
}