| VK Cup 2012 Квалификационный раунд 2 |
|---|
| Закончено |
Маленькая Танечка любит играть в кубики. Вообще-то она любит играть во что угодно, будь то кубики или тессеракты, лишь бы это «что угодно» было разноцветное. Каждый кубик характеризуется двумя параметрами — цвет ci и размер si. Зебробашней называется башня, состоящая из кубиков ровно двух цветов, причем цвета кубиков в башне должны чередоваться (цвета соседних должны отличаться). В Зебробашне должно быть не менее двух кубиков. Каких-либо других ограничений нет. Ниже на рисунке изображен пример Зебробашни.
Высота Зебробашни — это сумма размеров всех кубиков, которые в нее входят. Помогите маленькой Танечке построить Зебробашню наибольшей возможной высоты, используя имеющиеся кубики.
В первой строке записано целое число n (2 ≤ n ≤ 105) — количество кубиков. В следующих n строках заданы описания кубиков, по одному описанию в строке. Описание кубика состоит из записанных через пробел двух целых чисел ci и si (1 ≤ ci, si ≤ 109) — цвет i-го кубика и его размер, соответственно. Гарантируется, что существует хотя бы два кубика, цвета которых различны.
Выведите описание Зебробашни максимальной возможной высоты в следующем формате. В первую строку выведите высоту башни, во вторую строку — количество кубиков в ней, в третью — номера кубиков в башне в порядке их перечисления снизу вверх, разделенные одиночными пробелами. Считайте кубики пронумерованными от 1 до n в том порядке, в котором они были заданы во входных данных.
Если существует несколько Зебробашен максимальной высоты, разрешается вывести любую из них.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
4
1 2
1 3
2 4
3 3
9
3
2 3 1
2
1 1
2 1
2
2
2 1
