Задача №111427. Студенческие годы
Вася не выполнил ни одной лабораторной работы в этом семестре, поэтому его отчисляют. Наконец, под угрозой отчисления, Вася решил начать учиться.
Вася должен выучить N различных дисциплин, для этого по каждой из них ему необходимо выполнить Ki лабораторных работ. Вася решил, что он сначала выполнит все лабораторные работы по одному из предметов, затем по другому и т.д.
Вася, мягко говоря, запоздал с выполнением работ, поэтому каждый преподаватель будет требовать с Васи взятку в размере w·t иностранных тугриков, где w — коэффициент сложности работы, а t — время сдачи работы. Если Вася начал выполнять лабораторную работу, то он не остановится ни перед чем, пока не закончит ее выполнение.
Вася знает сложность каждой лабораторной работы wj и время tj, которое ему потребуется на ее выполнение. Помогите ему выбрать такой порядок выполнения работ, чтобы суммарный размер взяток был минимален.
Все работы пронумерованы числами от 1 до T, где T = K1 + ... + KN, первые K1 работ относятся к первому предмету, следующие K2 ко второму предмету и т.д.
В первой строке входных данных содержится одно число N — количество предметов (1 ≤ N ≤ 500). Далее содержатся числа Ki — число лабораторных работ по соответствующему предмету (1 ≤ Ki ≤ 100).
В следующей строке содержится T целых чисел pj — времена выполнения соответствующих работ (1 ≤ pj ≤ 10 000).
В последней строке содержится T целых чисел wj, обозначающих коэффициенты сложности соответствующих работ (1 ≤ wj ≤ 10 000).
(student.in, student.out) В первой строке выведите одно число — искомую минимальную величину взяток. В следующей строке выведите перестановку чисел от 1 до T, обозначающих порядок выполнения работ в оптимальном расписании. Помните, что Вася сначала должен изучить какой-то один предмет целиком, а только потом приступить к следующему и также изучать его целиком. В случае, если существует несколько решений, выведите любое из них.
1
5
1 2 3 4 5
5 4 3 2 1
70
1 2 3 4 5
2
2 2
1 1 2 2
1 1 2 2
23
1 2 3 4