"Stupid LaTeX!" Bob said, "How can it so difficult to learn!"
Recently, Bob is writing a paper about the Avengers and he suffers from learning LaTeX for typesetting. He thinks the typesetting algorithm of LaTeX is shit therefore he wants to develop a new typesetting system himself.

Having finished the GUI development, Bob finds it is impossible to design a typesetting algorithm by himself. So he comes to you for help.

Here is the problem. A paper contains many sentences. Several sentences can be put in one line, separated by spaces. There is no restrictions on the number of sentences in a single line, but a sentences cannot be separated into two lines and the order of the sentences cannot be changed. Bob has a perfect line length L in his heart, and he wants the length of each line in the paper is close to the perfect line length. Bob also defines the chaos score of a line to be:



where n is the number of sentences in the line, L_i is the length of the i-th sentence, P is a positive integer. Furthermore, the chaos score of a paper is:



where m is the total number of the lines in the paper.

Given a paper, Bob want to know the minimal chaos score.

The first line of input contains a single integer, T (1<=T<=65), indicating the number of test cases.
In each test case, the first line contains three integers, N (1<=N<=10^5), L (1<=L<=3*10^6), and P (1<=P<=10). N indicates the number of sentences in the paper, L indicates the perfect line length, and P is the exponent in the definition of chaos score.
In the following N lines, each line contains a string. The string is composed of English letters, digits, and visible characters whose ASCII ranges from 33 to 127 (except '-').
All sentences are no longer than 30 characters.

For each test case, output one line.
If the minimal chaos score is less than 10^18, output an integer indicating the minimal chaos score, and output "-1" (DO NOT output the quote symbols) otherwise.

4
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet

108
32
-1
1000000000000000000

The typesetting results of each test case:

Case 1:
brysj,
hhrhl.
yqqlm,
gsycl.

Case 2:
brysj, hhrhl.
yqqlm, gsycl.

Case 3:
The minimal chaos score is larger than 10^18.

Case 4:
poet