e-olymp
Соревнования

Azerbaijan Programming Olympiad - 2nd Stage preparation

Буфкрафт

Бренда наслаждается новой ролевой игрой Буфкрафт. Щиты, мечи, книги и другая ручная кладь не влияет на статус персонажа в Буфкрафт. Единственный способ увеличить статус Вашего персонажа - забодать его.

В Буфкрафте имеются две бодалки. Прямая бодалка увеличивает базовое значение статуса, в то время как процентная бодалка увеличивает базовое значение на некоторый процент. Если начальное значение статистики Вашего персонажа равно b, после чего Вы его отбодали n прямыми бодалками с силой d1, d2, ..., dn и m процентными бодалками с силой p1, p2, ..., pm, то результирующий статус будет равен (b + d1 + d2 + ... + dn)(100 + p1 + p2 + ... + pm) / 100. Отметим, что результат может иметь вид дроби.

К несчастью, у Вашего героя имеются лишь k слотов для бодания, и если Вы забодаете его больше k раз, то лишь последние k боданий останутся активными. Поэтому нет смысла совершать более k боданий одновременно. Одно и то же бодание накладывать более одного раза на персонажа нельзя.

Бренда собирается отправить своего персонажа в поход и хочет увеличить его здоровье до максимально возможного значения. Она имеет в своем распоряжении несколько прямых и процентных боданий и просит Вашей помощи выбрать из них такой набор, который даст персонажу максимально возможное значение здоровья.

Входные данные

Первая строка содержит четыре целых числа b, k, cd и cp - базовое здоровье героя, число слот для бодания, количество доступных прямых боданий и количество доступных процентных боданий.

Следующая строка содержит cd целых чисел di - силы прямых боданий.

Последняя строка содержит cp целых чисел pi - силы процентных боданий.

Все числа больше или равны нулю, и не более пятидесяти тысяч.

Выходные данные

В первой строке вывести два числа n и m - количество прямых и процентных боданий (0ncd, 0mcp, 0n + mk), которые будут использованы.

В следующей строке вывести n различных чисел - индексы применяемых прямых боданий (бодания нумеруются с единицы).

В последней строке вывести m разных чисел - индексы применяемых процентных боданий (также нумеруются с единицы).

Результирующее здоровье после применения всех n + m боданий должно быть наибольшим.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
70 3 2 2
40 30
50 40
Выходные данные #1
2 1
1 2 
1 
Входные данные #2
1 2 3 4
6 6 5
8 10 7 9
Выходные данные #2
2 0
2 1 

Источник 2014 ACM NEERC, Northern Subregion, November 8, Problem B