JBOI 2017 will be a different type of a competition. There will be N problems, all printed on paper for each contestant. Each problem is made up of at most M words. Each page that the problems will be printed on can contain up to K lines and up to P characters on a single line. The committee has decided on the following constraints in regards to how to print the problems for one contestant:

- Each problem has to start and end on the same page. You can assume this will always be possible.
- The problems have to appear in the order that they are given in the input. There has to be one blank line between consecutive problems if they appear on the same page.
- The words in each problem have to appear in the order that they are given as well. There has be to be a single space between consecutive words if they appear on the same line.
- The first word in each line must start at the beginning of the line.
- Each word has to start and end on the same line.

Keeping in mind these constraints, the committee wants to minimize the printing costs, which is calculated as the sum of the total cost of all problems and the total cost of all pages, where:

- The cost of a problem. The words of each problem, are split in different lines so that no word gets out of the paper bound. The cost of each line is the unused space at the end of the line SQUARED. The cost of a problem is the sum of the costs of each, except the last, line used for the problem.
- The cost of a page. The cost of a page is the number of unused lines at the bottom of the page. Note that the line between different problems doesn’t exist if the problems are on different pages, so every line after the last problem on a page is considered to be unused.

Input

line 1: N (1 ≤ N ≤ 400), the number of problems, K (M ≤ K ≤ 600) the number of lines that can fit on a single page, and P (10 ≤ P ≤ 100), the number of characters that can fit on a single line on that page.

next N lines: first M (1 ≤ M ≤ 400), the number of words in the corresponding problem, and then M integers, the number of characters in the words of the problem. These numbers will all be between 1 and 20, inclusive.

Output

line 1: the minimal printing cost that can be achieved.

Note: It is always possible to print the given problems.

Constraints

Time limit: 1 second
Memory limit: 64 megabytes

Examples

input
3 7 15
5 6 8 5 9 1
4 7 6 6 14
3 9 1 2

output
74

Explanation: The minimal printing cost can be achieved if the problems are printed on two pages (Page 1 and Page 2) as shown on the following images:

The cost of the first problem is 0. Line 1: 6 + 1 + 8 = 15 (note that the +1 is the space between the words, not a word). Line 2: 5 + 1 + 9 = 15. The last line always comes for free, and it contains only the last word, with length 1.

For the second problem, the word with length 7 is on the first line, the two words with length 6 are printed on the second line, and the word with length 14 is on the third line. This gives a cost of: (15 - 7)² + (15 - (6 + 1 +6))² + 0 = 64 + 4 = 68.

All the words in the third problem fit in a single line. The cost of that line would have been (15 - (9 + 1 + 1 + 1+ 2))² = 1, but since it’s a last line its cost is 0 instead, which is the cost of this problem.

Since the number of lines that can fit on a single page is 7, as shown on the images the optimal solution can be accomplished when the first two problems are put on the first page and the third problem is on the second page.

The cost of the first page is 0 since the first two problems occupy exactly 7 lines.

The cost of the second page is 6, since 6 of the lines on that page will be left unused.

So, the total cost of all the problems is 0 + 68 + 0 = 68, and the total cost of all the pages is 0 + 6 = 6. Therefore, the printing cost is 68 + 6 = 74.