Задача №3898. Два капитана
Капитаны Флинт и Джек Воробей нашли клад и хотят поделить его. Клад находится в шкатулке и состоит из чётного числа драгоценных камней. Капитан Флинт оценил \(i\)-ый камень в \(a_i\) пиастров, а Джек Воробей — в \(b_i\) долларов. Теперь они действуют следующим образом. Джек Воробей достаёт из шкатулки два камня, после чего Флинт забирает себе один из них (естественно, тот, у которого больше \(a_i\)). Оставшийся камень достаётся Воробью. После этого Джек Воробей достаёт ещё пару камней, и так далее: каждым ходом Воробей достает из шкатулки два камня, Флинт забирает себе камень с большим \(a_i\), оставшийся камень достается Воробью.
Джек Воробей знает все \(a_i\), все \(b_i\), а также может, доставая очередные два камня, подглядеть в шкатулку и выбрать, какие именно камни надо доставать. Помогите ему действовать так, чтобы доля Воробья была максимально возможной (т.е. чтобы сумма \(b_i\) полученных Воробьём камней была как можно больше).
По сравнению с камнями шкатулка ничего не стоит, поэтому её можно не учитывать при дележе.
Первая строка входного файла содержит одно целое число \(N\) — количество камней в кладе. Гарантируется, что \(N\) чётное и что \(2\leq N\leq 5000\). Далее следуют две строки по \(N\) целых чисел в каждой: сначала заданы все \(a_i\), потом — все \(b_i\). Гарантируется, что все \(a_i\) различны (т.е. что действия Флинта всегда однозначно определены). Гарантируется, что все \(a_i\) и все \(b_i\) положительны и не превосходят \(400\,000\).
В выходной файл выведите \(N/2\) строк по два числа в каждой — пары камней, в том порядке, как их должен доставать из шкатулки Джек Воробей. Камни нумеруются начиная с 1.
Числа в пределах каждой пары можете выводить в произвольном порядке. Если есть несколько оптимальных решений, выводите любое.
Среди тестов будут такие, в которых каждый камень оба капитана оценивают одинаково: \(a_i=b_i\) для каждого \(i\) (как во втором тесте из примера); суммарная стоимость таких тестов будет 40 баллов.
6 6 10 11 18 5 14 1 7 6 12 15 16
5 1 2 3 6 4
6 6 44 2 43 7 48 6 44 2 43 7 48
3 1 5 4 2 6