Slot Machine
Limits: 2 sec., 256 MiB
Zenyk wants to win a prize on a slot machine. Slot machine consists of \(N\) boxes. \(i\)-th box contains \(L_i\) balls, each ball has a color \(C_{ij}\).
On each turn Zenyk pays one coin, chooses one box and gets one random ball from chosen box. He wins a prize if he gets two balls of the same color. Now Zenyk is interested what is the minimum number of coins he needs to pay to guarantee winning the prize. That means that for any sequence of balls he get on each turn he can obtain 2 balls of the same color. Note that Zenyk can decide which box to choose after previous turn.
Help Zenyk to find this number.
Input
First line of the input contains one integer \(N\). Each of the next \(N\) lines contains integer \(L_i\) followed by \(L_i\) integers \(C_{ij}\) – colors of the balls in the \(i\)-th box.
It’s guaranteed that there is at least one pair of balls with the same color.
Output
Print one number – minimum number of coins.
Constraints
\(1 \le N \le 10^5\),
\(1 \le L_i \le 10^5\),
\(\sum_{i=1}^n L_i \le 10^5\),
\(1 \le C_{ij} \le 10^5\).
Samples
Input (stdin) | Output (stdout) |
---|---|
7 4 1 2 3 4 1 1 1 2 1 3 1 4 7 4 7 4 4 7 7 4 1 5 | 2 |
Notes
At first Zenyk chooses first box and then one of the boxes 2-5 depending on the color of the ball he get.
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 |
---|