背景

官方spj：https://www.luogu.org/paste/03wjc4ne

spj provider: @hehezhou

题目描述

物理学家栋栋最近在研究一个能量场。在这个能量场中有 $n$ 个粒子，每个粒子都有两个属性：质量 $m$ 和结合系数 $c$。

栋栋发现，在这个能量场中，每个粒子都有两极，N 极和 S 极。两个粒子相遇时，符合“同极相斥，异极相吸”的原则，只能是一个粒子的 N 极和另一个粒子的 S 极连接到一起。当质量为 $m_a$，结合系数为 $c_a$ 的粒子 $a$ 的 N 极与另一个质量为 $m_b$，结合系数为 $c_b$ 的粒子 $b$ 的 S 极直接连接时，可以产生大小为 $m_am_b(c_a-c_b)$ 的结合能量。

请解决以下两个问题：

1. 在能量场的 $n$ 个粒子中哪两个粒子直接连接的能量最大。
2. 栋栋发明了一种方法，能选择其中的任意 $k$ 个粒子 $p_1,p_2,\dots,p_k$，将 $p_i$的 N 极与 $p_i+1$ 的 S 极连接 $(1\le i<k)$，$p_k$ 的 N 极与 $p_1$ 的 S 极连接，其中 $p_1,p_2,\dots,p_k$ 两两不同。$k$ 可以在 $1$ 至 $n$ 中任意取值，如使用栋栋的这种方法连接，选择哪些粒子可以得到最大的能量。

输入格式

第一行包含一个整数 $n$ ，表示粒子的个数。

接下来 $n$ 行，每行两个实数，第 $i+1$ 行的两个实数表示第 $i$ 个粒子的质量 $m_i$ 和结合系数 $c_i$。$(0<m_i,c_i<10^5)$

输出格式

第一行包含两个整数 $a,b$，表示将粒子 $a$ 的 N 极与粒子 $b$ 的 S 极连接可以得到最大的能量。

第二行包含一个整数 $k$，表示第二问中要得到最大的能量需要多少个粒子。第三行包含 $k$ 个整数，表示 $p_1,p_2,\dots,p_k$，即第二问中的最优方案。

4  
1.0 2.0 
3.0 1.0 
5.0 4.0 
2.0 2.0

3 2 
3  
1 3 2

提示

【样例说明】
对于第一问，第三个粒子的N极与第二个粒子的S极连接，能得到的能量为 $5\times3\times(4-1) = 45$。

对于第二问，顺次连接 $1,3,2$ 号粒子，能量为 $1\times5\times(2-4)+5\times3\times(4-1)+3\times1\times(1-2)=32$。

【数据规模】

$10\%$ 的数据，$n\le 8$；

$20\%$ 的数据，$n\le 15$；

$40\%$ 的数据，$n\le 1000$；

$50\%$ 的数据，$n\le 5000$；

$100\%$ 的数据，$n\le 50000$。

【评分标准】

此题可能有多解，如果用你的解产生的能量与参考答案的绝对误差或相对误差小于 $10^{–5}$，则得满分。否则不得分。
对于本题，每问的分数各占 $50\%$。如果你的输出任何一问的格式或结果不正确，则不得分；否则如果其中的一问正确，则得到该测试点 $50\%$ 的分数；如果两问都正确，得到该测试点 $100\%$ 的分数。