Problem O
Initials
When marking computer science assignments, markers like to mark each student in order of how they are listed in class. The way the class is listed is quite strange though, a class is sorted by concatenating the first name to the last name (for example Harry Potter becomes PotterHarry) and all upper case letters are turned to lower case. Then sorting those strings lexicographically is the order of the class. Each student needs a Unix directory for the marker to put their assignments in.
Since the marker is lazy, he decides to create a directory for each student only using their initials (first letter of last name followed by the first letter of first name). The marker soon realizes that the way Unix sorts the directories, students are no longer sorted in the correct order and there are now duplicate folder names. Oh no! This must be fixed.
For each name, we are allowed to add $0$ or more letters from the original name to the initials, except you must always use the first $k$ unchosen letters in the initials. For example, the initials of Harry Potter are PH. Adding $2$ letters make it PotH, adding $6$ letters makes it PotterHa.
The markers come to you for help. Your job is to write a program which tells the markers the minimum number of letters they need to add to put all the students into correct sorted order, so that all resulting “extended” initials are unique.
For example, in the sample input below, the initials (sorted) would be (HA, HB, ZZ). By adding three letters we get (HaB, HatA, ZZ) which is the correct sorted order.
Input
The first line contains a single integer $2 \leq N \leq 1000$ indicating the number of students. Then follow $N$ lines, each containing two strings: the first and last name of the student. The first and last name each contains at least one character, and they consist of only lowercase and uppercase English alphabetic letters. The combined length of each student name will be at most $80$ characters. No two students will have the same concatentated name (as described above).
Output
A single number on a line by itself, the minimum number of letters that need to be added to put all the students in sorted order.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 Bob Harris Andrea Hat Zanny Zan |
3 |
