TAP2012D - Designing T-Shirts

[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/taip2012-problems.pdf]

 

Argentina's rugby is currently in one of its best moments of
all time. Recently the under-18 and under-21 national teams
qualified for their corresponding world cups, so the coaches of
both teams have asked the Incredible Commission for the
Production of Clothing (ICPC) to provide the t-shirts for these
events. Each team is formed by N players, but because the two
world cups do not take place simultaneously it was agreed that
the ICPC would provide only N t-shirts, to be used by both
teams.
For this reason, the t-shirts must be a valid set of clothing
for both teams. The rules if the rugby world cups state that
each player must go in the field with a t-shirt imprinted with
a unique number, along with a prefix of the player's surname,
not necessarily unique. This includes boundary cases such as a
t-shirt with no surname prefix (that is, a prefix of length 0)
and a t-shirt with a complete surname.
The experts of ICPC immediately realized that they could simply
provide N t-shirts with only numbers and no surnames on them,
and each of them would be a valid t-shirt to be used by any
player. However, the coaches would rather have the t-shirts
with the longest possible prefixes, of course without violating
world cup rules, because this way it's easier for them to
identify the players while the matches are taking place.
Your task is to help the ICPC finding the maximum amount of
letters that can be imprinted on a set of N t-shirts, so that
this set is a valid clothing set for both teams. For example,
if we have N=3 players, the under-18 team is composed of
"PEREZ", "GONZALEZ" and "LOPEZ", whereas the under-21 team is
composed of "GARCIA", "PERALTA" and "RODRIGUEZ", the optimal
choice consists in having one t-shirt with the 1-letter prefix
"G" (to be used by "GONZALEZ" and "GARCIA"), another one with
the 3-letter prefix "PER" (to be used by "PEREZ" and
"PERALTA"), and the third t-shirt with a 0-letter prefix (to be
used by "LOPEZ" and "RODRIGUEZ"). This way, the answer in this
case would be 1+3+0=4.

Argentina's rugby is currently in one of its best moments of all time. Recently the under-18 and under-21 national teams qualified for their corresponding world cups, so the coaches of both teams have asked the Incredible Commission for the Production of Clothing (ICPC) to provide the t-shirts for these events. Each team is formed by N players, but because the two world cups do not take place simultaneously it was agreed that the ICPC would provide only N t-shirts, to be used by both teams.

For this reason, the t-shirts must be a valid set of clothing for both teams. The rules of the rugby world cups state that each player must go in the field with a t-shirt imprinted with a unique number, along with a prefix of the player's surname, not necessarily unique. This includes boundary cases such as a t-shirt with no surname prefix (that is, a prefix of length 0) and a t-shirt with a complete surname.

The experts of ICPC immediately realized that they could simply provide N t-shirts with only numbers and no surnames on them, and each of them would be a valid t-shirt to be used by any player of any of the two teams. However, the coaches would rather have the t-shirts with the longest possible prefixes, of course without violating world cup rules, because this way it's easier for them to identify the players while the matches are taking place.

Your task is to help the ICPC finding the maximum amount of letters that can be imprinted on a set of N t-shirts, so that this set is a valid clothing set for both teams. For example, if we have N = 3 players, the under-18 team is composed of "PEREZ", "GONZALEZ" and "LOPEZ", whereas the under-21 team is composed of "GARCIA", "PERALTA" and "RODRIGUEZ", the optimal choice consists in having one t-shirt with the 1-letter prefix "G" (to be used by "GONZALEZ" and "GARCIA"), anotherone with the 3-letter prefix "PER" (to be used by "PEREZ" and "PERALTA"), and the third t-shirt with a 0-letter prefix (to be used by "LOPEZ" and "RODRIGUEZ"). This way, the answer in this case would be 1+3+0=4.

 

Input

Each test case is described using three lines. The first line contains a single integer number N, indicating the number of players in each of the two teams (1 ≤ N ≤ 104). The second line contains the surnames of the N players in the under-18 team, whereas the third line contains the surnames of the N players in the under-21 team. Each surname is a non-empty string of at most 100 uppercase letters. In each test case the total number of characters in the 2N surnames is at most 105, and two or more players of the same or different teams may have the same surname.

The end of the input is indicated by a line containing the number -1.

 

Output

For each test case, you should print a single line containing an integer number, representing the maximum number of letters that can be imprinted on a set of N valid t-shirts to be used by both teams as explained in the problem statement.

 

Example

Input:
3
PEREZ GONZALEZ LOPEZ
GARCIA PERALTA RODRIGUEZ
2
RODRIGO GONZALEZ
GONZALO RODRIGUEZ
3
LOPEZ PEREZ LOPEZ
PEREZ LOPEZ LOPEZ
1
GIMENEZ
JIMENEZ
6
HEIDEGGER GAUSS GROTHENDIECK ERDOS CHURCH TURING
HEISENBERG GALOIS EULER ALLEN GODEL CHURCHILL
-1

Output:
4
12
15
0
13

Added by:Fidel Schaposnik
Date:2012-10-04
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2012

hide comments
2016-08-16 08:06:39 nabila ahmed
The following test case helped me
Input:
2
OSE
ADITY
AD
ADI
-1
Output:
3

Last edit: 2016-08-16 08:08:02
2016-06-28 05:37:25
AC in first go :D
2015-06-10 19:39:59 Whatever
@Mulkit09 did u find the problem , i am also getting WA
2015-03-22 20:01:50 Mukit09
Getting WA... Can anyone post some sample input please?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.