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 <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);

double w[100000];
double v[100000];
typedef pair<double,int> pdi;
double a[100000];
const double EPS = 1e-8;

int main() {
  int N;
  double W;
  cin >> N >> W;  
  
  vector<pdi> vec1, vec2;
  double ans = 0;
  REP(i, N) {
    cin >> w[i] >> v[i];
    if (w[i]>0 && v[i]>0) {
      vec1.push_back(pdi((double)v[i]/w[i], i));
    } else if (w[i]<0 && v[i]<0) {
      w[i] = abs(w[i]);
      v[i] = abs(v[i]);
      vec2.push_back(pdi((double)v[i]/w[i], i));
    } else if (w[i]>0 && v[i]<=0) {
    } else if (w[i]<=0 && v[i]>=0) { 
      ans += v[i];
      W += abs(w[i]);
    }
  }
  sort(ALL(vec1), greater<pdi>());
  sort(ALL(vec2));
  memset(a,0,sizeof(a));
  int j = 0;
  for (int i=0; i<vec1.size(); ++i) {
    int idx = vec1[i].second;
    if (w[idx]<=W) {		// 1 wariate
      ans += v[idx];
      W -= w[idx];
    } else {
      ans += v[idx] * W/w[idx];
      a[idx] = W/w[idx];
      W = 0;
      while(a[idx] < 1) {
      //while(w[idx]>W+EPS) {
	if (j >= vec2.size() || vec2[j].first >= vec1[i].first) {
	  break;
	}
	int jdx = vec2[j].second;
	double hoge = min(w[idx]*(1-a[idx])/w[jdx], 1-a[jdx]);
	a[jdx] += hoge;
	double hoge2 = (w[jdx]*hoge)/w[idx];
	//cout << "hoge = " << hoge << endl;
	//cout << "hoge2 = " << hoge2 << endl;
	a[idx] += hoge2;
	ans += v[idx] * hoge2;
	//cout << "ans1 = " << ans  << endl;
	ans -= v[jdx] * hoge;
	//cout << "ans2 = " << ans << endl;
	if (a[jdx] > 1-EPS) j++;
      }
      //cout << "!!" << 1-a[idx] << endl;
    }
    //cout << W << ":  " << ans << endl;
  }
  printf("%.10f\n", ans);
}