창하의 급식실 탁자 이야기

시간 제한1초메모리 제한1024 MB

요약

서로 다른 무리의 학생끼리 이웃하거나 마주 보지 않도록 2 x M 격자에 앉힐 때, 가능한 M의 최솟값을 구한다.

문제

KSA 급식실에는 긴 직사각형 탁자 하나가 있으며, 이 탁자는 두 명이 서로 마주 보고 앉는 $2\times M$ 격자 모양으로 되어 있다.

학생들은 자신이 함께 점심을 먹고 싶은 친구들과 무리를 지어 점심을 먹는데, 무리의 개수는 총 $N$ 개이다. 모든 학생들은 정확히 하나의 무리에 속하며 한 명으로 구성된 무리도 존재할 수 있다. 서로 다른 무리에 속한 학생들은 이웃하거나 마주 보고 앉을 수 없다.

예를 들어 $M = 3$ 인 아래의 상황에서 학생 A와 서로 다른 무리에 속한 학생은 빗금친 의자에 앉을 수 없다.

KSA 예산 관리자인 창하는 예산을 절약하기 위해 $M$ 을 최소한으로 줄이고자 한다. 모든 학생들이 동시에 앉을 수 있는 방법이 존재하도록 $M$ 의 최솟값을 구해주자.

첫 번째 줄에 무리의 개수를 나타내는 정수 $N$$(1 \le N \le 2 \times 10^5)$ 이 주어진다.

다음 $N$ 개의 줄 중 $i$ 번째 줄에 $i$ 번째 무리에 속한 학생 수가 주어진다. 각 무리의 학생 수는 $1$ 명 이상 $2 \times 10^5$ 명 이하이다.

학생들이 모두 탁자에 동시에 앉을 수 있는 방법이 존재하도록 하는 $M$ 의 최솟값을 출력한다.