本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn

1350. Algorithm Teaching


Description

The Latin American Beginners Regional Contest is coming, and the University of Byteland wants to prepare a team of newly-admitted students to compete. The university has N teachers that can instruct students in the topic of algorithms. Each candidate student must be trained by a single teacher, in a non-empty subset of the algorithms that the teacher knows. For example, if a given teacher knows the two algorithms PRIM and KRUSKAL, then the teacher can train a student just on PRIM, just on KRUSKAL, or on both PRIM and KRUSKAL. As you can see, in this case there are three different options for this particular teacher to train a student. In general, a given teacher that knows A different algorithms can train a student in \$2^A-1\$ different ways. All these \$2^A-1\$ options can be carried out, because the university haasa lot of new students, and there is no limit on the number of students a teacher can train.

The university would like to form a team having as many students as possible. However, each pair of students in the  nal team must be able to cooperate, which means that each one of them must have been trained on an algorithm that the other hasn't. For example, a student trained on BFS and DFS can cooperate with another student trained on DFS and DIJKSTRA, because the  rst student is trained on BFS while the second student isn't, and the second student is trained on DIJKSTRA while the  rst student isn't. On the other hand, a student trained on BFS and DFS cannot cooperate with another student trained just on BFS, or just on DFS, or on both BFS and DFS, among others.

Given the set of algorithms that each teacher knows, you must determine the maximum number of students in a team in which every student can cooperate with each other. Recall that each student must be trained by a single teacher, while each teacher can train as many students as needed. For example, if there is just one teacher who knows the algorithms DFS, BFS and DIJKSTRA, it is possible to prepare a team with up to three students: a  first student trained on DFS and BFS, a second student trained on DFS and DIJKSTRA, and a third student trained on BFS and DIJKSTRA.

Input

The  first line contains an integer \$N (1 \leq N \leq 100)\$ indicating the number of teachers. Each of the next \$ N \$ lines describes a teacher with an integer \$A (1\leq A \leq 10) \$ representing the number of algorithms the teacher knows, followed by A different non-empty strings of at most 10 uppercase letters each, indicating the names of the algorithms that teacher knows.

Output

Output a single line with an integer indicating the maximum number of students in a team in which every student can cooperate with each other.

Samples

Input Copy
1
3 DFS BFS DIJKSTRA
Output
3
Input Copy
2
4 BFS DFS LCA RMQ
2 PRIM KRUSKAL
Output
8
Input Copy
4
3 BFS DFS DIJKSTRA
4 BFS DFS LCA RMQ
3 DIJKSTRA BFS DFS
3 FLOYD DFS BFS
Output
10
Input Copy
1
1 HAVEFUN
Output
1
Input Copy
3
4 FFEK DANTZIG DEMOUCRON FFT
4 PRIM KRUSKAL LCA FLOYD
4 DFS BFS DIJKSTRA RMQ
Output
18

Source

ICPC Latin American Regional 2019
Problem Information

Time Limit: 2000MS (C/C++,Others×2)
Memory Limit: 256MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 0 / 5
Tags: test(1)
Contests involved

1039. ICPC Latin American Regional 2019
My history solutions

You didn't submit any solution!
Submit your solution

Login Register