28241번 - 교실 불 끄기

문제

송도고등학교의 경비원인 진서는 교실의 불을 모두 끄고 얼른 퇴근하고 싶다. 하지만 진서는 S리그 경기 중에 발생한 무릎 부상으로 인해 계단을 오르내리는 것이 매우 힘들다.

따라서 진서는 최소한의 계단을 사용하여 불을 끄는 방법 중 시간을 최소화하는 방법으로 불을 끌 것이다.

불을 끄러 다니는 경비원 진서의 피곤한 모습이다.

학교는 $n$개의 층으로 이루어져 있으며 모든 층에는 계단, $m$개의 교실, 계단이 순서대로 배치되어 있다. 각 교실과 계단은 하나의 칸으로서 표현된다. 한 칸을 이동하는 데에는 1ドル$분이 걸리고, 층간 이동은 계단을 통해서만 할 수 있다. 특히 학교 건물의 가장 높은 층인 $n$층에는 면학실이 있기에 모든 교실에 불이 켜져 있다.

예제로 주어지는 학교의 모습이다. 편의상 양 끝 계단 열에 0ドル$과 4ドル$를 부여했다.

진서가 학교의 1ドル$층 왼쪽 계단 칸에서 출발하여 모든 불을 끄고 마지막으로 1ドル$층 왼쪽 계단 칸 혹은 1ドル$층 오른쪽 계단 칸에 도달하는 시간(분)을 계산하는 프로그램을 작성하여라. 단, 진서가 각 교실의 불을 끄는 시간은 매우 짧으므로 고려하지 않는다.

입력

첫 번째 줄에는 학교의 층수 $n$과 한 층에 있는 교실의 수 $m$가 공백으로 구분되어 주어진다.

이어서 $n$개의 각 $i+1$번째 줄에는 $i$층에 있는 불이 켜진 교실의 수 $k_i$와 $k_i$개의 불이 켜진 각 교실이 왼쪽 계단 칸으로부터 떨어진 칸의 수 $a_{i,1}, a_{i,2}, \ldots, a_{i,k_i}$가 공백으로 구분되어 순서대로 주어진다.

출력

조건에 맞게 불을 다 끄고 나가는 문까지 도달하는 시간(분)의 최솟값을 출력한다.

제한

• 2ドル ≤ n , m ≤ 100,000円$.
• 0ドル ≤ k_i ≤ m$.
• $k_n = m$.
• 불이 켜진 모든 교실의 수는 100ドル,000円$ 이하.
• 1ドル \le a_{i,1} < a_{i,2} < \cdots < a_{i,k_i} \le m$.

노트

• C/C++의 경우, 32bit 정수형 int의 범위를 넘어가는 정수를 다루게 되므로 64bit 정수형 long long 사용을 권장한다.