Repair Works
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Our presidential candidates cannot pass by the hype of the 47th day of the year either. Some propose to make this holiday a national day off, others — to abandon unlucky numbers. And some even promise to double the number of lucky numbers.
One of the candidates decided to repair one of the roads in his hometown on this holiday. For simplicity, we will assume that the road is an infinite straight line, points on which correspond to the respective kilometer marks of the road.
For the repairs, the candidate hired \(n\) companies, each of which will repair a certain segment of the road. It is known that the \(i\)-th company will start repairs from the \(s_i\)-th kilometer of the road and will finish at one of \(t_{i,1}, ..., t_{i,c_i}\). Since the money for the work has already been transferred, the candidate must choose an ending kilometer for each of the companies, after which the companies will perform their work. Note that some companies may repair a part of the road that has already been repaired by another.
The candidate wants to make the best possible impression on voters. He believes that for this, the number of segments of the repaired road should be as large as possible. Help him find this maximum number by determining the ending kilometer of its work for each company.
Input
The first line gives a single integer \(n\) — the number of companies.
The next \(n\) lines describe the companies, one per line. The first two numbers describe \(s_i\) and \(c_i\) — the starting kilometer of the road and the number of ending options. Next are \(c_i\) numbers, each of which is one of the options for the kilometer where the company will finish its repair.
Output
In a single line, output one integer — the maximum number of repaired road segments.
Constraints
\(1 \le n, c_i, s_i, t_{i,j} \le 300\),
it is guaranteed that the sum of all \(c_i\) does not exceed \(300\), and also that \(t_{i, j} \ne s_i\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 2 2 1 3 4 1 7 3 2 2 4 | 2 |
Notes
In the example, two segments can be achieved as follows:
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|