Модуль искусственного интелекта GAIA под именем HEPHAESTUS успел сильно развиться и активно занимается производством машин, используя ресурсы системы, в которую встраивается. После того, как Бета выпустила HEPHAESTUS в компьютерную сеть «Далекого Зенита», он сразу составил план по производству $$$n$$$ машин, $$$i$$$-я из которых требует $$$a_i$$$ единиц ресурсов на производство.
Чтобы соптимизировать процесс, ИИ нашел способ сохранять ровно одну единицу ресурсов с каждых $$$100$$$ единиц, задействованных в производстве каждой отдельной машины. Иными словами, с производства машины стоимостью $$$a_i$$$ можно сохранить $$$\left\lfloor \frac{a_i}{100} \right\rfloor$$$ единиц ресурсов.
Желая соптимизировать производство машин еще больше, HEPHAESTUS организовал возможность производить машины в парах. Если произвести машины $$$i$$$ и $$$j$$$ в паре, будет сохранено $$$\left\lfloor \frac{a_i + a_j}{100} \right\rfloor$$$ единиц ресурсов.
Определите, какие машины следует объединить в пары, чтобы сэкономить как можно больше ресурсов. Из всех способов сэкономить наибольшее количество ресурсов следует выбрать тот, в котором как можно меньше машин объединены в пары, и как можно больше произведены самостоятельно.
В первой строке ввода записано целое число $$$n$$$ — количество машин, которые надо произвести ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$).
Во второй строке через пробел перечислены целые числа $$$a_1$$$, ..., $$$a_n$$$ — количество ресурсов, необходимое для производства каждой машины ($$$1 \leqslant a_i \leqslant 10^9$$$).
В первой строке выведите единственное целое число $$$t$$$ — максимальное количество ресурсов, которые можно сэкономить.
Во второй строке выведите целое число $$$k$$$ — минимальное необходимое для этого количество объединений машин в пары.
В следующих $$$k$$$ строках выведите пары номеров машин, которые следует объединить при производстве.
Если возможных ответов с данными $$$t$$$ и $$$k$$$ несколько, выведите любой из них.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 8 | $$$n \leqslant 3$$$ | – | полная |
2 | 14 | все $$$a_i$$$ равны между собой | – | полная |
3 | 14 | $$$a_i \leqslant 50$$$ для всех $$$i$$$ | – | полная |
4 | 18 | $$$n \leqslant 15$$$ | 1 | полная |
5 | 20 | $$$n \leqslant 1000$$$ | 4 | полная |
6 | 26 | нет | 1 – 5 | первая ошибка |
3 30 120 190
3 1 2 3
6 100 4 197 324 690 500
18 2 2 3 4 5