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 JAVA):

Solution:
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int N = sc.nextInt();
		double W = sc.nextInt();
		int[] w = new int[N];
		int[] v = new int[N];
		double ans = 0;
		for (int i = 0; i < N; ++i) {
			w[i] = Integer.parseInt(sc.next());
			v[i] = Integer.parseInt(sc.next());
			if (w[i] <= 0 && v[i] >= 0) {
				ans += v[i];
				W -= w[i];
			}
		}
		ArrayList<Product> add = new ArrayList<Product>();
		ArrayList<Product> sub = new ArrayList<Product>();
		for (int i = 0; i < N; ++i) {
			if (w[i] > 0 && v[i] > 0) {
				add.add(new Product(w[i], v[i]));
			} else if (w[i] < 0 && v[i] < 0) {
				sub.add(new Product(w[i], v[i]));
			}
		}
		Collections.sort(add);
		Collections.sort(sub);
		int addI = add.size() - 1;
		double addX = 1.0;
		int subI = 0;
		double subX = 1.0;
		while (addI >= 0) {
//			System.out.println(W + " " + ans + " " + addI + " " + addX + " " + subI + " " + subX);
			double needW = add.get(addI).w * addX;
			if (W == 0) {
				if (subI >= sub.size() || add.get(addI).e() < sub.get(subI).e()) break;
				double feedW = Math.abs(sub.get(subI).w) * subX;
				if (feedW < needW) {
					W += feedW;
					ans += sub.get(subI).v * subX;
					++subI;
					subX = 1.0;
				} else {
					double difX = needW / Math.abs(sub.get(subI).w);
					W = needW;
					ans += sub.get(subI).v * difX;
					subX -= difX;
				}
//				System.out.println("  " + W + " " + ans + " " + addI + " " + addX + " " + subI + " " + subX);
			}
			if (needW > W) {
				ans += add.get(addI).e() * W;
				addX -= W / add.get(addI).w;
				W = 0;
			} else {
				ans += add.get(addI).e() * needW;
				W -= needW;
				--addI;
				addX = 1.0;
			}
		}
		System.out.println(new BigDecimal(ans).toPlainString());
	}

	static class Product implements Comparable<Product> {
		int w, v;

		Product(int w, int v) {
			this.w = w;
			this.v = v;
		}

		double e() {
			return 1.0 * this.v / this.w;
		}

		public int compareTo(Product o) {
			return this.v * o.w - this.w * o.v;
		}
	}

}