← 返回题目列表

Codeforces · 159/E

E. 斑马塔

中文机器翻译题面 查看原题

小珍妮特喜欢玩立方体。事实上,她喜欢玩任何东西,无论是立方体还是超正方体,只要它们是彩色的。每个立方体由两个参数描述——颜色 ci 和大小 si。斑马塔是由两种颜色的立方体组成的塔。此外,塔中立方体的颜色必须交替(相邻立方体的颜色必须不同)。斑马塔应该至少有两个立方体。没有其他限制。下图显示了斑马塔的示例。

斑马塔的高度是构成该塔的所有立方体的尺寸之和。帮助小珍妮特使用可用的立方体搭建尽可能高的斑马塔。

输入

第一行包含一个整数 n (2 ≤ n ≤ 105) — 立方体的数量。接下来的 n 行包含立方体的描述,每行一个描述。立方体描述由两个空格分隔的整数 ci 和 si (1 ≤ ci, si ≤ 109) 组成 - 相应地,第 i 个立方体的颜色和大小。保证至少有两个不同颜色的立方体。

输出

用下面的表格打印最大高度斑马塔的描述。在第一行中打印塔的高度,在第二行中打印形成塔的立方体的数量,在第三行中按照立方体在塔中从底部到顶部的顺序打印空间分隔的索引。假设立方体按照输入中给出的顺序从 1 到 n 编号。

如果存在多个具有最大高度的斑马塔,则允许打印其中任何一个。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。

示例

输入 #1

4
1 2
1 3
2 4
3 3

输出 #1

9
3
2 3 1

输入 #2

2
1 1
2 1

输出 #2

2
2
2 1