Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3523

Time Limit: 4 Seconds      Memory Limit: 65536 KB

Because of the 90th anniversary of the Coherent & Cute Patchouli (C.C.P), Patchouli Knowledge decides to rearrange the books on her bookcase.


Patchouli Knowledge is a powerful magician who lives in Scarlet Devil Mansion. In Scarlet Devil Mansion there's a large library under the ground, and Patchouli Knowledge lives in it. Of course, it's dark and uncomfortable, however it's a good quiet place to do some research or study on new powerful magics.

In the library there's a large bookcase. For convenience, we assume that it has N levels of shelves. On each shelves there are M books. Of course, each book has a title, such as How to survive in Master Spark or Become a baka in nine minutes. Patchouli Knowledge reads a large number of books every day, so the bookcase is messy.

She decides to rearrange her books in ASCII order. For example, the book Two Dimension Mania should be put before the book Utawarerumono, and Zombies should be put before galgame. The books may have the same name, and the spaces are also considered when comparing titles in ASCII order.

Each time, she will choose one book from one shelf, and insert it in any place of the same shelf. However, because of asthma, it will cost her one unit of energy on each moves. Patchouli Knowledge is unable to do a lot of works. So she wants to know the minimal energy cost she need to rearrange all the books.


There are multiple test cases. For each test case:

The first line has two numbers N (1 <= N <= 50) as the level of the shelves and M (1 <= M <= 50) as the number of the books on each shelf.

Then followed by N blocks, each block describes a shelf that contains M lines. Each line of a block is a string (no more than 50 characters) indicates a book's title on the shelf. We assume all titles only have A to Z, a to z and spaces.


For each test case, output the answer as the description required.

Sample Input

2 2
Two Dimension Mania
Two Dimension Mania

Sample Output



In the first shelf, you need not to do anything; In the second shelf, you need to take the Two Dimension Mania out, and insert it before Utawarerumono.

Author: DAI, Longao
Submit    Status