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 - 2
// Greedy Method
// given N number of items and a W weight bag .
// Each item consists a weight w (-10<=w<=10) and it's corresponding value v(-10<=v<=10) .
// Fill the bag with this item but not overflow and also maximize the profit .
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
struct ABC
{
    double w , v , u ;
};
bool cmp(ABC A,ABC B)
{
    return A.u > B.u ;
}
vector <ABC> list ;
int main()
{
    int N ;
    double W ;
    scanf("%d%lf",&N,&W);
    double profit = 0.0 ;
    for(int i=0;i<N;i++)
    {
        ABC obj ;
        scanf("%lf%lf",&obj.w,&obj.v);
        obj.u = obj.v / obj.w ;
        if(obj.w>=0&&obj.v<=0) continue ; // Not consider the item .
        if(obj.w<=0&&obj.v>=0)
        {
            W-=obj.w;
            profit+=obj.v;
            continue;
        } // Must take item .
        if(obj.w<=0&&obj.v<=0)
        {
            W-=obj.w;
            profit+=obj.v;
            obj.w*=-1.0;
            obj.v*=-1.0;
        }
        list.push_back(obj);
    }
    sort(list.begin(),list.end(),cmp);

    for(int i=0;i<list.size()&&W!=0.0;i++)
    {
        if(list[i].w<=W)
        {
            W-=list[i].w;
            profit+=list[i].v; // Take the item .
        }
        else
        {
            profit+=list[i].u*W; // take the item .
            W=0.0;
        }
    }
    printf("%.8lf\n",profit);
    return 0;
}
/*
5 10
4 20
5 24
3 25
1 10
2 5
*/
/*
Maximize value is : 64.600000
*/