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

typedef struct
{
  int w, v;
  double vdw;
} Goods;

class GreaterVDW
{
public:
  bool operator() (const Goods& lhs, const Goods& rhs)
  {
    return lhs.vdw > rhs.vdw;
  }
};

int main()
{
  int N, W;
  while (cin >> N >> W) {
    double ans = 0.0;
    vector<Goods> goods;
    goods.reserve(N);
    for (int i = 0; i < N; ++i) {
      int w, v;
      scanf("%d %d", &w, &v);
      if (w >= 0 && v <= 0) {
	continue;
      } else if (w <= 0 && v >= 0) {
	W -= w;
	ans += v;
      } else {
	Goods g;
	g.w = w;
	g.v = v;
	if (g.w < 0 && g.v < 0) {
	  g.w = -g.w;
	  g.v = -g.v;
	  W += g.w;
	  ans -= g.v;
	}
	g.vdw = v / (w * 1.0);
	goods.push_back(g);
      }
    }
    sort(goods.begin(), goods.end(), GreaterVDW());

    for (unsigned int i = 0; i < goods.size(); ++i) {
      if (W < goods[i].w) {
	ans += (W / (goods[i].w * 1.0)) * goods[i].v;
	break;
      } else {
	ans += goods[i].v;
	W -= goods[i].w;
      }
    }
    printf("%.6f\n", ans);
  }
  return 0;
}