시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB46131244.444%

문제

하늘이는 휴가를 나가고 싶다.

휴가를 나가기 위해서는 $1$번 간부부터 $N$번 간부까지 총 $N$명의 간부에게 차례대로 결재를 받아야 한다.

최근 간부가 사무실을 비우는 일이 잦기 때문에 하늘이는 최대 $M$명의 간부의 결재를 건너뛰는 것을 승인받았다.

$i$번 간부는 $k_i$개의 시간 구간에 부재하며, 구체적으로는 $[l_{i,1}, r_{i, 1})$, $[l_{i,2}, r_{i, 2})$, $\cdots$, $[l_{i,k_i}, r_{i, k_i})$의 시간에 사무실을 비운다. 왼쪽은 닫혀있고 오른쪽은 열린 구간임에 유의하여라.

이때 $l_{i, 1} < r_{i, 1} < \cdots < l_{i, j} < r_{i,j} < \cdots < l_{i, k_i} < r_{i, k_i}$ 이다. 즉, 각 시간 구간은 길이가 0보다 크며, 동일한 간부의 부재중인 시간 구간은 서로 겹치지 않고 끝점을 공유하지도 않는다.

하늘이는 $0$초에 결재를 받기 시작하며 하늘이의 이동 시간 및 결재를 받는 시간은 $0$이라고 가정한다. 즉, 동시에 여러 명의 간부에게 결재를 받을 수도 있다. 만약 하늘이가 간부를 찾아갔을 때 부재중이라면 간부가 사무실에 복귀하는대로 결재를 받는다.

하늘이는 한시가 급하기 때문에 결재를 건너뛸 간부를 적절히 선택하여 최대한 빠른 시간 안에 최종 결재를 받으려고 한다. 최대한 빨리 결재를 받는다면 언제 최종 결재를 받을 수 있을지 구해보자.

입력

첫번째 줄에 $N$, $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100,000$, $0 \leq M \leq N$)

다음으로 $N$개의 줄에 걸쳐 $k_i$와 $l_{i,1}$, $r_{i, 1}$, $\cdots$, $l_{i,k_i}$, $r_{i, k_i}$가 공백으로 구분되어 주어진다.

($0 \leq k_i \leq 3 \times 10^5 $, $\sum {k_i} \leq 3 \times 10^5$, $0 \leq l_{i, 1} < r_{i, 1} < \cdots < l_{i, j} < r_{i,j} < \cdots < l_{i, k_i} < r_{i, k_i} \leq 10^9$)

모든 입력은 정수이다.

출력

최대 $M$명의 간부를 건너뛰고 결재를 받았을 때 가장 빠른 최종 결재 시간을 출력한다.

예제 입력 1

3 1
1 0 2
1 1 3
1 0 1

예제 출력 1

1

예제 입력 2

3 0
1 0 2
2 0 1 2 3
1 3 4

예제 출력 2

4

예제 입력 3

3 1
1 0 10
2 0 5 10 20
1 5 15

예제 출력 3

15

$1$번 간부는 $[0, 10)$, $2$번 간부는 $[0, 5)$ 및 $[10, 20)$, $3$번 간부는 $[5, 15)$의 시간에 부재한다.

이때 $1$번 간부를 건너뛰고 결재를 받는다면, $5$의 시각에 $2$번 간부에게 결재를 받은 후 $15$의 시각에 $3$번 간부에게 결재를 최종적으로 받을 수 있다.

출처

Contest > 보라매컵 > 제6회 보라매컵 F번