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>
#include <functional>
#pragma warning(disable : 4996)
using namespace std;
int N, W, w[100009], v[100009], cnt; vector<pair<double, int> > d1, d2;
double solve(double x) {
	double ret = 0.0, sum1 = 0.0, sum2 = 0.0;
	for (int i = 0; i < d1.size() && d1[i].first > 0.0; i++) {
		if (sum1 + d1[i].second < W + x) {
			ret += d1[i].first * d1[i].second;
			sum1 += d1[i].second;
		}
		else {
			ret += d1[i].first * (W + x - sum1);
			break;
		}
	}
	for (int i = 0; i < d2.size(); i++) {
		if (sum2 + d2[i].second < x) {
			ret += d2[i].first * d2[i].second;
			sum2 += d2[i].second;
		}
		else {
			ret += d2[i].first * (x - sum2);
			break;
		}
	}
	return ret;
}
int main() {
	scanf("%d%d", &N, &W);
	double sum = 0.0, sum2 = 0.0;
	for (int i = 0; i < N; i++) {
		scanf("%d%d", &w[i], &v[i]);
		if (w[i] == 0) sum += max(v[i], 0);
		if (w[i] > 0) d1.push_back(make_pair(1.0 * v[i] / w[i], w[i]));
		if (w[i] < 0) d2.push_back(make_pair(-1.0 * v[i] / w[i], -w[i])), sum2 -= w[i];
	}
	sort(d1.begin(), d1.end(), greater<pair<double, int> >());
	sort(d2.begin(), d2.end(), greater<pair<double, int> >());
	double l = 0.0, r = sum2;
	for (int i = 0; i < 90; i++) {
		double m1 = (l * 2.0 + r) / 3.0;
		double m2 = (l + r * 2.0) / 3.0;
		if (solve(m1) < solve(m2)) l = m1;
		else r = m2;
	}
	printf("%.10lf\n", solve(l) + sum);
	return 0;
}