#6809. 「THUPC 2022 初赛」赛程制定

题目描述

Lewis 热爱打拳，因此他组建了一家拳击俱乐部，希望通过举办表演赛卖票以筹集自己训练的资金。但是，很遗憾，Lewis 人缘并不好，因此这个俱乐部只有两个成员——Lewis 和他的好基友 Valtteri。观众们很快就厌倦了每晚都是他们两人出场的表演赛，票卖不出去了，拳击俱乐部濒临倒闭。穷则思变，Lewis 决定通过请外援的方式，尝试拯救自己的俱乐部。

通过支票攻势，Lewis 很快就请到了两个拳坛明星——Max 和 Checo，他们将作为飞行嘉宾加入 Lewis 的俱乐部。

在接下来的一个赛季里，Lewis 总共会安排 $n$ $(1 \le n \le 2\times 10^5)$ 场比赛，每场比赛会从现有的 4 个成员中选出 2 人比赛。

对于第 $i$ $(1 \le i \le n)$ 场比赛：

• 如果是 Lewis 和 Valtteri 的比赛，只能卖出 $a_i$ 元的门票；
• 如果是他们中一人和一个明星的比赛，能卖出 $b_i$ 元的门票；
• 如果是两个明星 Max 和 Checo 之间的比赛，能卖出 $c_i$ 元的门票。

观众们喜欢看明星之间的高水平比赛，而不是 Lewis 和 Valtteri 的菜鸡互啄，因此有：

[ 1 \le a_i < b_i < c_i \le 10^9 ]

除此之外，安排比赛时还有如下要求：

1. 明星档期限制
   因为明星都是日理万机的，他们只同意分别在 Lewis 的俱乐部停留最多 $t_m$、$t_c$ 场比赛的时间。
   设 Max 出席的第一场比赛是第 $p_m$ 场，最后一场是第 $q_m$ 场，Checo 出席的第一场比赛是第 $p_c$ 场，最后一场是第 $q_c$ 场，则需满足： [ q_m - p_m + 1 \le t_m, \quad q_c - p_c + 1 \le t_c ]

2. Lewis 不与明星比赛
   Lewis 深知自己不会是两个明星的对手，他不会安排自己与两位明星的比赛（因此挨打的工作被安排给了 Valtteri）。

3. “Lewis 的最优方案”定义
   对于一种方案，可以看作一个长度为 $2n$ 的序列，序列的第 $2i-1$ 和 $2i$ 项为第 $i$ 场比赛的对阵双方。
   如果通过修改序列的任意 $1$ 个位置，都无法得到一个收入严格大于当前收入的合法方案，则称此方案为 Lewis 的最优方案。

4. 随机选择与中位数
   Lewis 会从所有“Lewis 的最优方案”（两个方案相同，当且仅当每一天的对阵均相同，注意：Max vs Valtteri 和 Checo vs Valtteri 视为不同方案）中等概率随机选一个方案执行。
   问：在 Lewis 可能最终选择的所有方案中，门票收入的中位数是多少？（答案保留一位小数输出）

---

输入格式

第 1 行：3 个正整数 $n$, $t_m$, $t_c$，意义见题面；

接下来 $n$ 行：每行 3 个正整数 $a_i$, $b_i$, $c_i$ 表示三种情况下卖出的门票价格。

---

输出格式

一行一个数表示在 Lewis 最终选择的所有方案中，门票收入的中位数，保留一位小数输出。

---

样例 1

输入

2 1 1
1 10 100
1 2 3

输出

12.0

解释
Lewis 的“收入最大方案”总共有以下 4 种：

1. Max vs Checo, Lewis vs Valtteri，门票收入为 $100 + 1 = 101$
2. Valtteri vs Max, Valtteri vs Checo，门票收入为 $10 + 2 = 12$
3. Valtteri vs Checo, Valtteri vs Max，门票收入为 $10 + 2 = 12$
4. Lewis vs Valtteri, Max vs Checo，门票收入为 $1 + 3 = 4$

中位数为 $(12 + 12) / 2 = 12$。

---

样例 2

输入

3 1 3
1 2 3
5 6 12
1 5 6

输出

14.0

---

数据范围与提示

数据范围： [ 1 \le n, t_m, t_c \le 2\times 10^5 ]