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 <utility>
#include <iomanip>
using namespace std;

int main() {
	double answer=0;
	int N,W;
	cin >> N >> W;
	double w[N], v[N];
	for(int i=0; i<N; i++){
		cin >> w[i] >> v[i];
		if(w[i]<=0 && v[i]>=0){
			W-=w[i];
			answer+=v[i];
			w[i]=0;
			v[i]=0;
		}else if(w[i]>=0 && v[i]<=0){
			w[i]=0;
			v[i]=0;
		}
	}
	

	pair<double,double> plus[N], minus[N];	
	for(int i=0; i<N; i++){
		if(w[i]>0){
			plus[i].first=w[i]/v[i];
			plus[i].second=w[i];
			minus[i].first=0;
			minus[i].second=0;
		}else if(w[i]<0){
			minus[i].first=w[i]/v[i];
			minus[i].second=w[i];
			plus[i].first=0;
			plus[i].second=0;
		}
	}
	sort(plus,plus+N);
	sort(minus,minus+N);
	
	int p=0, m=N-1;	//plus, minus
	while(p<=N-1 && W-plus[p].second>=0){
		if(plus[p].first==0){
			p++;
			continue;
		}
		W-=plus[p].second;
		answer+=plus[p].second/plus[p].first;
		p++;
	}
	if(p==N){
		cout << fixed << setprecision(6) << answer << endl;
		return 0;
	}
	
	answer+=W/plus[p].first;
	plus[p].second-=W;
	W=0;
	if(plus[p].second==0){
		p++;
	}
	while(p<=N-1 && m>=0){
		if(minus[m].first<=plus[p].first){break;}
		
		if(-minus[m].second>plus[p].second){
			answer+=plus[p].second/plus[p].first;
			answer-=plus[p].second/minus[m].first;
			minus[m].second+=plus[p].second;
			p++;
		}else if(-minus[m].second<plus[p].second){
			answer-=minus[m].second/plus[p].first;
			answer+=minus[m].second/minus[m].first;
			plus[p].second+=minus[m].second;
			m--;
		}else if(-minus[m].second==plus[p].second){
			answer+=plus[p].second/plus[p].first;
			answer-=plus[p].second/minus[m].first;
			p++;
			m--;
		}

	}
	cout << fixed << setprecision(6) << answer << endl;
	return 0;
}