eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

От сессии до сессии живут студенты весело...

От сессии до сессии живут студенты весело...

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

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

В этом семестре Вася изучает N учебных предметов, по каждому из которых необходимо сдать K_i лабораторных работ (1 ≤ i ≤ N). Вася понимает, что делать лабы по нескольким предметам одновременно невозможно, поэтому он решил изучить один из предметов, а потом сделать все работы по этому предмету. После этого Вася займётся следующей дисциплиной...

Сдавать лабы, относящиеся к одному и тому же предмету, можно в произвольном порядке, но преподаватели выставляют штрафные баллы за их несвоевременную сдачу. Размер штрафа зависит от срока сдачи конкретной работы и равен

w_j·t_j, 1jT (T = K_i)

где w_j — коэффициент, установленный преподавателем, а t_j — время сдачи работы.

Время выполнения каждой лабораторной работы (конечно, после изучения дисциплины) известно и составляет p_j, 1 ≤ j ≤ T.

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

w_j·t_j

станет минимальной. Предполагается, что все работы делаются сразу же одна за другой, а временем на изучение предмета можно пренебречь.

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

Первая строка файла содержит величину N (1 ≤ N ≤ 500). Во второй строке записаны N величин K_i (1 ≤ K_i ≤ 100). Третья строка содержит T чисел — величины p_j (1 ≤ j ≤ T), где вначале идут работы, соответствующие первому предмету, затем — второму, и т.д. Наконец, четвёртая строка содержит величины w_j в таком же формате. Все величины p_j, w_j — целые, положительные, не превосходящие 10000.

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

В первой строке выведите искомую величину штрафа (целое число), которую необходимо минимизировать. Во второй строке запишите перестановку из T чисел, которая обеспечивает получение такого штрафа. Если задача допускает несколько решений, выведите любое из них.

Пример

Входные данные #1
1
5
1 2 3 4 5
5 4 3 2 1
Выходные данные #1
70
1 2 3 4 5
Источник NEERC Western Subregional Contest 2012