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:
//Fractional Knapsack
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Material{
	int w, v;
	bool operator<(const Material& val)const{ return 1.0*v*val.w < 1.0*val.v*w; };
};

int main(){
	cout.precision(16);
	int N, W;
	vector<Material> M;
	M.reserve(100000);
	double CurW = 0.0;//現在のW値
	double Max = 0.0;//求める最大値
	//入力
	cin >> N >> W;
	{
		Material temp;
		for (int i = 0; i < N; ++i){
			cin >> temp.w >> temp.v;
			if (temp.w < 0){
				if (temp.v >= 0){//w- && v0+ -> 必ず使用(x=1)
					CurW += temp.w;
					Max += temp.v;
				} else{//w- && v- -> 使用したことにして符号合わせ
					CurW += temp.w;
					Max += temp.v;
					temp.w *= -1; temp.v *= -1;
					M.push_back(temp);
				}
			} else if (temp.v > 0){//w0+ && v+ -> v/w大の順に使用
				M.push_back(temp);
			}
			//w0+ && v0- -> 必ず不使用(x=0)/無視
		}
	}
	sort(M.begin(), M.end());
	//w,v同符号 -> v/w大の順に使用
	for (vector<Material>::reverse_iterator it = M.rbegin(); it != M.rend(); ++it){
		if (CurW + it->w <= W){//W超えない -> x=1.
			CurW += it->w;
			Max += it->v;
		} else{//W超える1つめ -> x=適正値.break.
			Max += double(W - CurW) / it->w * it->v;
			break;
		}
	}
	//出力
	cout << Max << endl;

	return 0;
}