Задача №112118. Штурм
Автоботы отважились на штурм базы десептиконов. Из-за эффекта внезапности множество десептиконов полегло на месте, а остальные начали судорожно прятаться в бункеры, которые начали закрываться. Оптимус Прайм хочет добить как можно больше десептиконов. Для этого он решил использовать новую разработку автоботов — бомбу «Антибункер».
Принцип работы бомбы заключается в том, что ее можно кинуть внутрь бункера, а когда тот закроется — взорвать, и тогда она убьет всех, кто был внутри. Единственное ее неудобство заключается в том, что взрывается она неавтоматически. То есть Оптимусу, после того, как он кинет бомбу, придется ждать закрытия бункера, чтобы взорвать всех внутри, и лишь потом он сможет поехать дальше.
Оптимус собирается проехать мимо каждого бункера ровно один раз, посетив их в порядке возрастания номеров. К счастью, он знает, на какой минуте закроется каждый из бункеров, а также количество десептиконов в каждом из бункеров. Между бункерами Оптимус перемещается очень быстро — перемещение между любой парой бункеров занимает у него ровно одну минуту. Если он проехал бункер, он уже не сможет вернуться обратно.
Оптимус Прайм просит вас помочь ему рассчитать, какое наибольшее количество врагов он сможет убить, и в какие бункеры нужно бросить бомбу для этого.
В первой строке дано число n ( 1 ≤ n ≤ 10 5 ) — количество бункеров.
Далее идут две строки по n целых чисел. В первой строке содержатся числа a i ( 1 ≤ a i ≤ 10 9 ) — количество десептиконов в бункере i . Во второй строке содержатся числа t i ( 1 ≤ t i ≤ 10 5 ) — время закрытия бункера i .
В первой строке выходного файла выведите одно число — наибольшее возможное количество врагов, которые будут повержены Оптимусом. Во второй строке выведите количество бункеров, которое он сможет взорвать. Во третьей строке выведите через пробел номера бункеров, которые будут взорваны. Номера должны следовать по возрастанию. Из условия понятно, что момент закрытия каждого взорванного бункера должен быть больше, чем момент закрытия бункера, взорванного перед ним.
Первая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 1000 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 60 баллов.
Вторая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 10 5 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.
3 1 2 1 1 2 3
4 3 1 2 3
5 4 1 5 9 3 9 7 9 8 8
10 2 2 4