package chelper; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.TreeSet; import io.InputReader; import io.OutputWriter; import misc.GCJSolution; public class TaskC extends GCJSolution { private Comparator comparator = new Comparator() { @Override public int compare(double[] o1, double[] o2) { int t = Double.compare(o1[0], o2[0]); if (t != 0) { return t; } return -Double.compare(o1[1], o2[1]); } }; private int n; private double p; private double[] w; private double[] h; public void solve(int testNumber, InputReader in, OutputWriter out) { wrapSolve(testNumber, in, out); } void add(TreeSet s, double l, double r) { double[] x = {l, r}; if (s.contains(x)) { return; } while (true) { double[] y = s.floor(x); if (y != null && x[0] <= y[1]) { x[0] = Math.min(x[0], y[0]); s.remove(y); } else { break; } } while (true) { double[] y = s.ceiling(x); if (y != null && x[1] >= y[0]) { x[1] = Math.max(x[1], y[1]); s.remove(y); } else { break; } } s.add(x); } @Override public void solve(int testNumber) { n = in.nextInt(); p = in.nextDouble(); w = new double[n]; h = new double[n]; for (int i = 0; i < n; i++) { w[i] = in.nextDouble(); h[i] = in.nextDouble(); } List a = new ArrayList<>(); double min = 0; for (int i = 0; i < n; i++) { min += (w[i] + h[i]) * 2; double[] j = {Math.min(w[i], h[i]) * 2, Math.hypot(w[i], h[i]) * 2}; a.add(j); } a.sort(comparator); TreeSet s = new TreeSet<>(comparator); s.add(new double[]{0, 0}); for (double[] x : a) { TreeSet ns = new TreeSet<>(comparator); add(ns, x[0], x[1]); for (double[] y : s) { add(ns, y[0], y[1]); add(ns, x[0] + y[0], x[1] + y[1]); } s = ns; } double best = 0; p -= min; for (double[] x : s) { if (x[0] <= p) { best = Math.max(best, Math.min(p, x[1])); } } out.println(best + min); } }