ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2016

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Технический долг

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
Паша недавно пришёл на свое первое место работы. Паша — опытный ACM-щик, и ему сразу доверили доработку крупного модуля системы, над которым работало несколько поколений разработчиков. Не все они были опытными и умелыми, поэтому в исходном коде накопился существенный технический долг: баги, неоправданное дублирование, сложная запутанная логика и другие раздражающие проблемы.
«Так жить нельзя! Надо срочно всё переписать!» — воскликнул Паша, едва открыв среду разработки. Оправившись от шока, Паша оценил суммарный объем технического долга числом X. К сожалению, строгий менеджер не даёт ему целыми днями переписывать старый код и заставляет решать всякие нужные для клиентов задачи. Всего Паша должен решить N Очень Важных клиентских задач.
Паша читал Фаулера и понимает, что технический долг снижает полезность реализации новых задач. Немного подумав, для каждой задачи i Паша определил ai — объем технического долга, который можно закрыть в процессе её решения, и bi — ее полезность. Теперь каждую из N задач он будет решать следующим образом:
  • Сначала Паша перепишет часть исходного кода, мгновенно уменьшив технический долг на ai. Конечно, технический долг не может стать меньше нуля.
  • Затем Паша напишет код, который непосредственно решает поставленную задачу. В идеальном мире этот код принёс бы проекту bi пользы, однако в реальной системе, в которой есть технический долг X', решение задачи принесёт лишь max(0, biX') пользы.
Паша — хороший программист, и написанный им код технический долг не увеличивает (по крайней мере, он так думает).
Строгий менеджер хочет получить от решения всех задач как можно больше пользы, при этом до размера технического долга менеджеру нет дела. В каком порядке Паша решает задачи, менеджеру тоже без разницы. Помогите Паше установить такой порядок задач, чтобы суммарная польза от их решения была максимальной.

Исходные данные

В первой строке через пробел записаны два целых числа X и N (0 ≤ X ≤ 100, 1 ≤ N ≤ 200). Во второй строке даны N целых чисел a1, a2, …, an (0 ≤ ai ≤ 100). В третьей строке даны N целых чисел b1, b2, …, bn (0 ≤ bi ≤ 106).

Результат

В первой строке выведите максимальную суммарную пользу, которую можно получить после решения N задач. Во второй строке выведите перестановку из N чисел — номера задач в порядке, в котором их должен решать Паша. Если вариантов ответа несколько, выведите любой из них.

Примеры

исходные данныерезультат
5 3
0 1 5
5 1 0
6
3 2 1 
4 4
3 0 1 2
7 8 2 3
19
1 4 3 2 
Автор задачи: Никита Бурлаков
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2084. Технический долг