Ця задача відрізняється від попередньої задачі «Друк бюлетенів (коротка відповідь)» лише потребою вивести детальнішу відповідь; більш того, формат вхідних даних цілком однаковий, а перше число відповіді цієї задачі якраз і є єдиним числом відповіді попередньої.

Однією з багатьох проблем технічної підготовки до виборів є друк бюлетенів. Щоб забезпечити належний ступінь захисту, всі бюлетені друкують на одному поліграфічному комбінаті. Оскільки на бюлетенях вказують номер округу, поліграфкомбінату доводиться мати справу з ~N~ різними замовленнями (де ~N~ – кількість округів); виконувати ці замовлення можна лише послідовно одне за одним; для бюлетенів кожного ~i~-го округу відомий час друкування ~t_{i,1}~.

Бюлетені на різні округи може відвозити різний транспорт. Причому, цього транспорту достатньо, щоб ні при якому порядку друку не виникало затримок, пов'язаних з його (транспорту) очікуванням. Тим не менш, перевезення бюлетенів кожного ~i~-го округу все ж займає значний час ~t_{i,2}~.

Момент остаточної готовності до виборів настає тоді, коли бюлетені вже доставлені в усі округи.

Напишіть програму, яка визначатиме такий порядок друку бюлетенів, щоб проміжок часу від початку друкування до моменту остаточної готовності був якомога меншим.

Вхідні дані

У першому рядку вказана кількість округів ~N~ (~2\leqslant N \leqslant 10^5~), наступні ~N~ рядків містять по два натуральні числа кожен – час друкування ~t_{i,1}~ та час доставки ~t_{i,2}~ бюлетенів відповідного округу. Усі значення ~t_{i,1}~ та ~t_{i,2}~ в межах ~2\leqslant t\leqslant 10^4~.

Результати

Перший рядок має містити знайдений мінімальний час від початку друкування до моменту остаточної готовності. Наступні ~N~ рядків повинні задавати порядок друку замовлень. Тобто, спочатку номер округа, з якого слід почати друк бюлетенів, потім номер округа, бюлетені якого слід друкувати наступним, і так далі. Якщо можливі різні порядки, які забезпечують однаковий мінімальний час, слід вивести будь-який один з них.

Приклади

Вхід

3
10 5
5 20
5 5

Результат

25
2
1
3

Вхід

4
10 5
5 12
25 8
12 6

Результат

57
3
4
2
1