E. Зебробашня
ограничение по времени на тест
1.5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Маленькая Танечка любит играть в кубики. Вообще-то она любит играть во что угодно, будь то кубики или тессеракты, лишь бы это «что угодно» было разноцветное. Каждый кубик характеризуется двумя параметрами — цвет 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