15983번 - 순간이동 발판 서브태스크

국제 소 줄서기 사진 콘테스트에서 우승한 현욱은 우승 상금을 흥청망청 쓰면서 여행을 다니다 어느 마녀에게 붙잡히고 말았다. 마녀는 현욱이 도망치지 못하게 성 앞에 거대한 미궁을 만들어 놓았고, 마녀로부터 도망치기 위해선 이 미궁을 헤쳐나가 미궁의 출구에 도달해야 한다.

미궁은 1차원의 긴 선분 모양이며, 0부터 100만까지의 정수 좌표로 구역이 나누어져 있다. 이 사이에는 순간이동 발판들이 있는데, 이들은 매초 미궁 내의 다른 구역으로 순간이동한다. 이때 그 발판 위에 올라가 있던 사람도 함께 순간이동시킨다. 두 발판이 서로 같은 구역에 있을 때 현욱은 다른 쪽 발판으로 갈아탈 수 있으며, 현욱은 민첩해서 갈아타는 데에는 시간이 소요되지 않는다. 또한 구역들 사이의 간격이 넓기 때문에 서로 다른 구역으로 발판을 이용하지 않고 그냥 뛰어서는 건널 수 없다.

발판들은 순간이동 주기가 있어 각자의 주기만큼이 지나면 다시 처음의 위치로 순간이동하여 반복한다. 각 발판은 주기 내에서 같은 구역에 2번 이상 나타나지 않는다. 또한 두 발판이 방문하는 구역은 최대 한 곳을 제외하고 서로 다르며, 한 구역에는 최대 2개의 발판만이 방문한다.

현재 시각은 0초이고, 발판은 총 N개 있으며 현욱은 첫 번째 발판 위에 올라있다. 첫 번째 발판은 0초일 때 좌표 0인 구역에서 시작하고, 다른 발판은 좌표 0에 방문하지 않는다. 또한 미궁의 출구가 있는 구역에는 최대 하나의 발판만이 방문한다.

마녀에게 잡아먹히기 전에 현욱은 최대한 빨리 미궁에서 탈출해야 한다. 현욱이 미궁에서 탈출하기까지 걸리는 시간은 최소 얼마일까?

첫째 줄에 발판의 수 N과 미궁의 출구가 위치한 구역의 좌표 E 가 공백을 사이에 두고 주어진다.

둘째 줄부터 각 발판의 정보가 주어진다. i번째 정보의 첫 줄에는 i번째 발판의 주기 K_i 가 주어지고, 다음 줄에 K_i개의 좌표가 주어진다. 주어지는 순서대로 0초일 때의 좌표, 1초일 때의 좌표, ... K_i - 1초일 때의 좌표이다.

모든 좌표는 10⁶ 이하의 음이 아닌 정수이고, 첫 번째 발판의 0초일 때의 좌표는 0임이 보장된다. 또한 입력 전체에서 같은 좌표가 3번 이상 나타나는 경우도 없다.

현욱이 미궁의 출구가 있는 구역에 도달하기 위한 최소 시간을 출력한다. 만약 도달하는 것이 불가능하다면 -1을 출력한다.

• 1 ≤ N ≤ 100
• 1 ≤ K_i ≤ 4000

•  1 ≤ K_i ≤ 50, 모든 발판의 주기는 동일하다

•  1 ≤ K_i ≤ 50

•  추가 제한 없음

예제 입력 2, 3, 4는 발판들의 주기가 모두 같지 않으므로 subtask1에 포함되지 않는다.