P14763 [Opoi 2025] CCD 的赌局

CCD 经营的赌场濒临倒闭，他只好玩点新花样。

**下方有形式化题意。** CCD 决定通过作弊的方式赢取利润，他邀请到了两个考场读错题此时痛不欲生的 Oier 小 L 和小 T 作为内部人员。 具体的，CCD 决定让小 L 和小 T 玩 $n$ 轮，每轮恰好有一人获胜。 CCD 为了借此机会捞一笔，大放广告吸引了一大群人前来下注（赌每一轮谁赢），为了让赌博看上去更有吸引力，所以 CCD 决定使**小 L 胜的单位返还金额与小 T 胜的单位返还金额之和为 $T$**。并且为了赚更多的钱，CCD 可以在中间某两轮之间更改单位返还金额，但是要求双方的总和仍然为 $T$，并且只能更改一次。但可惜的是，内部人员小 L 和小 T 早已和其他人私底下串通好了，**在每一轮中，他们总是会选择返还金额更大的结果**。（比如若小 L 在这一轮中胜利获得的返还金额比小 T 在这一轮中胜利获得的返还金额更大，小 L 和小 T 就会操控赌局结果使得小 L 获胜） 现在 CCD 通过某些手段知道了每一轮双方的下注金额，记为 $a_i,b_i$。他想要通过设定两次（或一次）的返还金额，使得他最后返还的金额最小，并求出这个值。 由于 CCD 数学不好，于是他向你求助。 > **单位返还金额和返还金额**：如果这一轮小 L 的单位返还金额为 $a$，小 T 的单位返还金额为 $b$，其他人押了 $x$ 块钱赌小 L 胜，$y$ 块钱赌小 L 胜，如果小 L 获胜那么返还金额就会增加 $a\cdot x$ 块钱，但是如果结果小 L 输了，返还金额就会增加 $b\cdot y$ 块钱。 ### 形式化题意 给定 $n$，$T$，以及两个实数序列 $a_{1\dots n}$，$b_{1\dots n}$。 你可以任意设定 $4$ 个非负实数 $A_1,B_1,A_2,B_2$ 以及一个整数 $k \in [0,n]$，使得他们满足 $T=A_1+B_1=A_2+B_2$。求如下式子的最小值： $$\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)$$ 特别的，当 $s > e$ 时，定义 $\sum\limits_{i=s}^{e} f(i)$ 的值为 $0$。

第一行一个整数 $n$，一个非负实数 $T$。 接下来 $n$ 行，第 $i$ 行两个非负实数 $a_i,b_i$，表示第 $i$ 轮对小 L 和小 T 下的注的和。

一行一个实数表示返还金额的最小值，四舍五入到小数点后二位。

### 样例解释 在第一轮之前时，设定小 L，小 T 的单位返还金额分别为 $0.75$，$0.25$。 在第一轮以后，更改小 L，小 T 的单位返还金额分别为 $0.25$，$0.75$。 此时返还金额有最小值 $\max(4\times 0.75,12\times 0.25)+\max(12\times 0.25,4\times 0.75)=6$。 --- ### 数据范围与约定 **本题采用捆绑测试。** $$ \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} $$ 对于所有数据，$2\le n \le 10^{5}$，$0 \le T,a_i,b_i \le 100$，且 $\forall i \in [1,n],0 < a_i + b_i$，输入文件中所有实数精确到两位小数。