The Merry Student Life During the Term...#3887
As Vasya Pupkin has completed no labs since the start of the term, the dean has threatened to expel him. Vasya would really like to avoid that, so, finally, he decided to get serious...
During this term, Vasya is enrolled in classes, and each of them asks for K_i labs (1 \leq i \leq N). Vasya realizes it's impossible to study all subjects at once, so he has decided to study one of them, then do all the labs in that subject, and only then turn to the next subject...
The labs in one subject can be done in any order, but the lab instructors will assign penalties for lab work that is turned in late. The penalty depends on the time when the work was actually turned in and equals w_j \cdot t_j for every 1 \leq j \leq T, where w_j is a coefficient given by the lab instructor, t_j is the time when the work for the lab is turned in, and T = K_i is the total number of labs to be done.
The time needed to perform the lab (after studying the subject, of course) is known for each lab and equals p_j for every 1 \leq j \leq T.
Help Vasya find the order of tackling the subjects that minimizes the total penalty
w_j \cdot t_j.
Assume that all labs are done immediately one after another and that the times to study the subjects are negligible compared to the lab times.
The first input line contains the integer (1 \leq N \leq 500). The second line contains the values of K_i (1 \leq K_i \leq 100). The third line contains integers, the values of p_j (1 \leq j \leq T), where the labs for the first subject are listed first, then the labs for the second subject, and so on. Finally, the fourth line contains the values of w_j in the same order. All the values p_j and w_j are positive integers not exceeding .
The first output line should contain the minimal total penalty (an integer). The second line should contain a permutation of the integers ... that achieves the minimal penalty. If there are several possible solutions, output any one of them.
Example 1