Məsələlər
От сессии до сессии живут студенты весело...
От сессии до сессии живут студенты весело...
После того, как Вася Пупкин не сдал ни одной лабораторной работы с начала семестра, декан намекнул ему о возможном отчислении. Васе очень не хочется этого, поэтому он решил, наконец, взяться за ум...
В этом семестре Вася изучает \textbf{N} учебных предметов, по каждому из которых необходимо сдать \textbf{K_i} лабораторных работ (\textbf{1} ≤ \textbf{i} ≤ \textbf{N}). Вася понимает, что делать лабы по нескольким предметам одновременно невозможно, поэтому он решил изучить один из предметов, а потом сделать все работы по этому предмету. После этого Вася займётся следующей дисциплиной...
Сдавать лабы, относящиеся к одному и тому же предмету, можно в произвольном порядке, но преподаватели выставляют штрафные баллы за их несвоевременную сдачу. Размер штрафа зависит от срока сдачи конкретной работы и равен
\includegraphics{https://static.e-olymp.com/content/93/93fac9bf80c119dd3dc15cac80ae6a465c389659.jpg}
\textbf{w_j·t_j}, \textbf{1} ≤ \textbf{j} ≤ \textbf{T} (\textbf{T} = \textbf{K_i})
где \textbf{w_j} --- коэффициент, установленный преподавателем, а \textbf{t_j} --- время сдачи работы.
Время выполнения каждой лабораторной работы (конечно, после изучения дисциплины) известно и составляет \textbf{p_j}, \textbf{1} ≤ \textbf{j} ≤ \textbf{T}.
Помогите Васе и определите такую последовательность изучения предметов и выполнения лабораторных работ, при которой суммарная величина штрафа
\includegraphics{https://static.e-olymp.com/content/ab/ab0073311beb50e104aed3a8a613e284afef34eb.jpg}
\textbf{w_j·t_j}
станет минимальной. Предполагается, что все работы делаются сразу же одна за другой, а временем на изучение предмета можно пренебречь.
\InputFile
Первая строка файла содержит величину \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{500}). Во второй строке записаны \textbf{N} величин \textbf{K_i} (\textbf{1} ≤ \textbf{K_i} ≤ \textbf{100}). Третья строка содержит \textbf{T} чисел --- величины \textbf{p_j} (\textbf{1} ≤ \textbf{j} ≤ \textbf{T}), где вначале идут работы, соответствующие первому предмету, затем --- второму, и т.д. Наконец, четвёртая строка содержит величины \textbf{w_j} в таком же формате. Все величины \textbf{p_j}, \textbf{w_j} --- целые, положительные, не превосходящие \textbf{10000}.
\OutputFile
В первой строке выведите искомую величину штрафа (целое число), которую необходимо минимизировать. Во второй строке запишите перестановку из \textbf{T} чисел, которая обеспечивает получение такого штрафа. Если задача допускает несколько решений, выведите любое из них.
Giriş verilənləri #1
1 5 1 2 3 4 5 5 4 3 2 1
Çıxış verilənləri #1
70 1 2 3 4 5