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

const int MAXN = 100005;

int N;
double W;
double w[MAXN], v[MAXN];

double V;
vector<pair<double,double> > A;

bool comp(const pair<double,double> &a, const pair<double,double> &b) {
  return a.second*b.first > b.second*a.first;
}

int main() {
  cin >> N >> W;
  for(int i = 0; i < N; ++i) {
    cin >> w[i] >> v[i];
  }

  V = 0;

  A.clear();
  for(int i = 0; i < N; ++i) {
    if(w[i] >= 0 && v[i] <= 0) {
      //
    } else if(w[i] <= 0 && v[i] >= 0) {
      W -= w[i];
      V += v[i];
    } else if(w[i] >= 0 && v[i] >= 0) {
      A.push_back(make_pair(w[i],v[i]));
    } else {
      W -= w[i];
      V += v[i];
      A.push_back(make_pair(-w[i],-v[i]));
    }
  }

  sort(A.begin(), A.end(), comp);
  for(int i = 0; i < A.size(); ++i) {
    double x = min(1.0, W/A[i].first);
    W -= A[i].first*x;
    V += A[i].second*x;
  }
  printf("%.6f\n", V);
  return 0;
}