시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 2048 MB76363258.182%

문제

You are the owner of a large successful internet site with lots of users. All these users have chosen an alias of exactly $l$ characters for logging into the site. Recently, you noticed that you started running into disk space issues: storing all these aliases takes up a lot of data!

You do not have enough money to buy extra storage, so you are looking for ways to reduce the storage space needed. A friend gives you the following compression idea that might help: instead of storing the full alias for each user, you might get away with only storing a prefix of that alias, as long as no other alias has the same prefix. For example, if you just have the aliases james and jacob, you can store only jam and jac and still be able to identify them both.

This idea sounds quite interesting to you, and you are looking forward to finally having more space available on your disk again. You would like to find out how much space you need to store all aliases using this compression technique.

입력

The input consists of:

  • One line with two integers $n$ and $l$ ($2 \le n \le 10^4$, $1 \le l \le 10^3$), the number of aliases and the length of each alias.
  • $n$ lines, each with an alias: a string consisting of exactly $l$ English lowercase characters (a-z). Each alias is unique.

출력

Output the total number of characters you still need to store if you apply this compression technique.

예제 입력 1

2 5
james
jacob

예제 출력 1

6

예제 입력 2

4 4
xxxx
yxxx
xxyx
yxxy

예제 출력 2

14

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2022 Preliminaries A번

  • 문제를 만든 사람: Ragnar Groot Koerkamp