Background

The casino run by CCD is on the verge of bankruptcy, so he has to try something new.

Problem Description

A formal statement is given below.

CCD decides to make profits by cheating. He invites two OIers, Xiao L and Xiao T, who are suffering after misreading an exam problem, to act as insiders.

Specifically, CCD lets Xiao L and Xiao T play $n$ rounds, and in each round exactly one person wins.

To take this chance to make a big profit, CCD advertises heavily and attracts a large crowd to bet (betting on who wins each round). To make the gambling look more attractive, CCD decides that the sum of the per-unit payout for Xiao L winning and the per-unit payout for Xiao T winning is $T$. Also, to earn even more money, CCD may change the per-unit payouts between two consecutive rounds, but the sum must still be $T$, and he can change them at most once. Unfortunately, the insiders Xiao L and Xiao T have already colluded with others in private: in each round, they will always choose the outcome with the larger payout. (For example, if the payout when Xiao L wins in this round is larger than the payout when Xiao T wins, then they will manipulate the result so that Xiao L wins.)

Now CCD somehow knows the total bet amounts on both sides in each round, denoted by $a_i, b_i$. He wants to set the payouts twice (or once) to minimize the total money he finally pays back, and asks you to compute this minimum value.

Per-unit payout and total payout: If in this round the per-unit payout for Xiao L is $a$ and for Xiao T is $b$, and other people bet $x$ dollars on Xiao L to win and $y$ dollars on Xiao L to win, then if Xiao L wins the total payout increases by $a\cdot x$ dollars; but if Xiao L loses, the total payout increases by $b\cdot y$ dollars.

Formal Statement

Given $n$, $T$, and two real sequences $a_{1\dots n}$, $b_{1\dots n}$.

You may choose any $4$ non-negative real numbers $A_1,B_1,A_2,B_2$ and an integer $k \in [0,n]$, such that $T=A_1+B_1=A_2+B_2$. Find the minimum value of the following expression:

$$\sum_{i=1}^{k}\max(A_1\times a_i, B_1 \times b_i) + \sum_{i=k+1}^{n}\max(A_2\times a_i, B_2 \times b_i)$$

In particular, when $s > e$, define $\sum\limits_{i=s}^{e} f(i)$ to be $0$.

Input Format

The first line contains an integer $n$ and a non-negative real number $T$.

The next $n$ lines each contain two non-negative real numbers $a_i,b_i$, meaning the total bet amounts on Xiao L and Xiao T in the $i$-th round.

Output Format

Output one real number: the minimum total payout, rounded to two digits after the decimal point.

2 1.00
4.00 12.00
12.00 4.00

6.00

Hint

Sample Explanation

Before the first round, set the per-unit payouts for Xiao L and Xiao T to $0.75$ and $0.25$, respectively.

After the first round, change the per-unit payouts for Xiao L and Xiao T to $0.25$ and $0.75$, respectively.

Then the minimum total payout is $\max(4\times 0.75,12\times 0.25)+\max(12\times 0.25,4\times 0.75)=6$.

---

Constraints and Notes

This problem uses bundled testdata.

$$\def\arraystretch{1.2} \begin{array}{|c|c|c|} \hline \begin{array}{c} \tt{subtask}\\\hline 1\\\hline 2\\\hline 3\\\hline \end{array} & \begin{array}{c} n\\\hline \le 10\\\hline \le 10^{3}\\\hline \le 10^{5}\\ \end{array} & \begin{array}{c} \tt{pts}\\\hline 10\\\hline 40\\\hline 50\\\hline \end{array} \\\hline \end{array}$$

For all testdata, $2\le n \le 10^{5}$, $0 \le T,a_i,b_i \le 100$, and $\forall i \in [1,n],0 < a_i + b_i$. All real numbers in the input file are accurate to two decimal places.

Translated by ChatGPT 5