Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3399
Classes Division

Time Limit: 3 Seconds      Memory Limit: 65535 KB

Here comes the new term. In this new term, there are N new students who enter Nobita's primary school. The president is busy with the classes division. Right now he is considering what is the best way to divide N students into no more than K classes so that they may cause the least amount of unhappiness in total.

But how to define and forecast the unhappiness students will cause in future? That's a question. Fortunately, Doraemon is nearly omnipotent. He tells the president that he can use an integer to describe a student's sentiment index, xi for the i-th student. Let L be the average of xi (i = 1, 2, ..., N). To simplify the problem, if L is not an integer, let it be the floor of itself. If the i-th student is sent into the k-th class, he will cause (xi - L)2 * gk units of unhappiness. Don't worry about the value of gk (k = 1, 2, ..., K), Doraemon can also tell them to the president.

Now it's the president's turn to determine the division. For some special reasons, the division should obey these following rules.

  • Let the number of classes be K1 (K1 <= K). These K1 classes should be numbered as 1, 2, ..., K1.
  • The number of students in a class should be no less than A and no more than B.
  • If the i-th student and the j-th student (i < j) are in the same class, then the l-th student (i < l < j) should be in the same class too.
  • If the i-th student is in the k1-th class and the j-th student is in the k2-th class where k1 < k2, then i should be less than j.
  • Each student should be sent to one and only one class.

The president can not find out the best division, so he turns to you for help. Remember that the total amount of unhappiness students cause is the sum of unhappiness each student causes. Your job is to figure out the minimum total amount of unhappiness and the best division. To simplify the problem, you are only asked to tell the number of classes K1 and the number of students in the K1-th class T.


There are multiple cases.

For each case, there are three lines. In the first line, there are four integers, N (1 <= N <= 10000), K (1 <= K <= 200), A (1 <= A <= N) and B (A <= B <= N), describe as above. The next line contains N integers, x1, x2, ... , xN (1 <= xi <= 100000). The last line contains K integers, g1, g2, ... , gK (-1000 <= gi <= 1000).


For each case, if there is no solution, output "No solution." in one line; otherwise, output three integers in a single line. The first is the minimum total amount of unhappiness. The second is the number of classes K1 follows, if there are multiple solutions to get the minimum total amount, output the smaller K1. Last is the number of students in the last class T, if there are still multiple solutions, output the smaller T.

There is a blank between cases.

Sample Input

10 3 1 4 
16 11 12 13 10 15 16 17 18 14
4 5 1

Sample Output

186 3 4

Author: MO, Luyi
Contest: ZOJ Monthly, September 2010
Submit    Status