От сессии до сессии живут студенты весело...
После того, как Вася Пупкин не сдал ни одной лабораторной работы с начала семестра, декан намекнул ему о возможном отчислении. Васе очень не хочется этого, поэтому он решил, наконец, взяться за ум...
В этом семестре Вася изучает N учебных предметов, по каждому из которых необходимо сдать K_i лабораторных работ (1 ≤ i ≤ N). Вася понимает, что делать лабы по нескольким предметам одновременно невозможно, поэтому он решил изучить один из предметов, а потом сделать все работы по этому предмету. После этого Вася займётся следующей дисциплиной...
Сдавать лабы, относящиеся к одному и тому же предмету, можно в произвольном порядке, но преподаватели выставляют штрафные баллы за их несвоевременную сдачу. Размер штрафа зависит от срока сдачи конкретной работы и равен
w_j·t_j, 1 ≤ j ≤ T (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 чисел, которая обеспечивает получение такого штрафа. Если задача допускает несколько решений, выведите любое из них.