28304번 - 다섯 용사의 검

당신은 오천 년 만에 봉인에서 깨어난 마왕을 물리치기 위해 모험을 떠났다. 당신은 숲속을 탐험하던 중 의문의 남자를 마주쳤다. 남자는 당신에게 다가오더니 다섯 개의 검을 내밀며 말했다.

“오천 년 전에 존재했던 다섯 명의 용사 중 가장 강력한 검을 가진 자만이 마왕을 봉인할 수 있었다. 이것은 그들에게 전수받은 검이다. 신중하게 선택하여라.”

각각의 검은 양의 정수인 공격력을 가지는데, 공격력이 얼마인지 맨눈으로 판별하기는 어렵다. 한때 견습 대장장이였던 당신은 각각의 검이 가질 수 있는 공격력 후보 집합을 알아냈다. 서로 다른 두 검의 공격력 후보 집합은 공통 원소를 가지지 않는다. 따라서 모든 검의 공격력은 서로 다르다.

당신은 남자에게 검의 공격력을 시험해 보겠다고 말했고, 남자는 승낙했다.

검을 시험하는 방법은 다음과 같다. 양의 정수 $m$을 정한 뒤, 주변에서 $m$의 단단함을 가진 바위를 찾아 다섯 개의 검으로 한 번씩 베어 본다. 바위에 균열이 난다면 검의 공격력이 $m$보다 높은 것이고, 그렇지 않다면 검의 공격력이 $m$보다 작거나 같은 것이다.

당신은 검을 여러 차례 시험해서 가장 강력한 검, 즉 가장 공격력이 높은 검을 찾고자 한다. 시험에 사용할 바위의 단단함은 이전 시험들의 결과를 보고 결정할 수 있다. 검의 공격력을 정확히 알아낼 필요는 없다. 가장 강력한 검이 무엇인지 찾아내기만 하면 된다.

당신은 최선의 방법으로 검을 시험하고자 한다. 모든 가능성을 따졌을 때, 검을 시험해야 하는 횟수의 최댓값이 가능한 한 작아야 한다. 당신이 최선의 방법으로 검을 시험한다면, 가장 강력한 검을 찾기 위해서는 최대 몇 번의 시험이 필요한가?

총 다섯 개의 줄이 주어진다.

$i$번째 줄의 맨 앞에는 $i$번째 검이 가질 수 있는 공격력 후보 집합 $A_i$의 크기가 주어진다. 그 다음 $A_i$의 원소들이 오름차순으로 주어진다. 모든 값은 공백으로 구분되어 주어진다.

각 $i$에 대해 공격력 후보 집합의 크기 $|A_i|$는 양의 정수이며, 모든 $|A_i|$의 합은 $50\ 000$ 이하이다.

주어지는 모든 공격력은 서로 다른 양의 정수이며, $10^9$ 이하이다.

당신이 최선의 방법으로 검을 시험한다면, 가장 강력한 검을 찾기 위해서는 최대 몇 번의 시험이 필요한지 출력한다.

첫 번째 예제에서, 만약 각 검의 공격력이 $1,30,2,20,3$이라면, 검을 시험하는 과정의 예시는 다음과 같다.

1. 먼저 $30$의 단단함을 가진 바위로 검을 시험한다. 시험 결과 모든 검이 바위에 균열을 내지 못한다.
2. 그 다음 $10$의 단단함을 가진 바위로 검을 시험한다. 시험 결과 $2,4$번째 검은 바위에 균열을 내고, $1,3,5$번째 검은 바위에 균열을 내지 못한다.

두 시험 결과에 따르면 $2$번째 검이 가장 강력하다는 사실을 알 수 있다. 각 검의 공격력이 어떻게 되더라도 마찬가지로 최대 두 번의 시험���로 가장 강력한 검을 찾을 수 있다.

두 번째 예제에서, 검을 시험하지 않아도 $3$번째 검이 가장 강력하다는 사실을 알 수 있다.