결근

결근(Absenteeism)은 정당한 이유 없이 의무나 책임을 습관적으로 이행하지 않는 행위이다.

Wikipedia

알렉스는 회사에서 일한다. 그와 함께 일하는 직원은 $n$명이다. 알렉스와 달리 직원들은 정해진 일정을 엄격히 지킨다. $i$번째 직원은 시각 $a_i$에 출근해서 시각 $b_i$에 퇴근한다 ($a_i < b_i$).

알렉스는 시각 0보다 일찍 출근할 수 없고, 시각 $m$보다 늦게 퇴근할 수 없다. 또한 하루에 $k$시간을 일해야 한다 ($k \le m$). 알렉스는 일하는 시간을 최대한 줄이고 싶어 한다. 하지만 동료들은 게으른 사람을 싫어한다. 동료 중 누구라도 알렉스가 하루에 $k$시간 미만으로 일한다는 것을 알아차리면 상사에게 불평하고, 알렉스는 해고된다.

알렉스가 시각 $x$에 출근하고 시각 $y$에 퇴근한다고 하자. 단, $0 \le x < y \le m$이다. 다음 조건 중 하나라도 성립하면 알렉스는 위험한 상태이다.

• $y - x < k$이고, $a_i \le x$이며 $y \le b_i$인 직원 $i$가 존재한다 (구간 $[x, y]$가 $[a_i, b_i]$에 완전히 포함된다). 이 경우 $i$번째 직원은 알렉스가 $k$시간 미만으로 일하는 것을 직접 본다.
• $x < a_i \le y \le b_i$이고, $y < k$인 직원 $i$가 존재한다. 이 경우 $i$번째 직원은 알렉스가 시각 $k$보다 일찍 퇴근하는 것을 본다.
• $a_i \le x \le b_i < y$이고, $x > m - k$인 직원 $i$가 존재한다. 이 경우 $i$번째 직원은 알렉스가 시각 $m - k$보다 늦게 출근하는 것을 본다.
• $y < a_i$ 또는 $b_i < x$이고 (구간 $[x, y]$와 $[a_i, b_i]$가 겹치지 않는다), $a_i \le k$이며 $b_i \ge m - k$인 직원 $i$가 존재한다. 이 경우 $i$번째 직원은 알렉스의 근무를 전혀 보지 못하지만, 알렉스가 $k$시간 동안 일할 수 없었다고 결론짓는다.

동료 중 누구도 상사에게 불평하지 않게 하면서, 알렉스가 근무하는 최소 시간은 얼마인가?

첫 줄에 세 정수 $n$, $m$, $k$ ($1 \le n \le 10^5$, $1 \le m \le 10^9$, $1 \le k \le m$)가 주어진다. 각각 직원의 수, 하루의 길이, 알렉스가 하루에 일해야 하는 시간이다.

이어지는 $n$개의 줄에는 두 정수 $a_i$와 $b_i$ ($0 \le a_i < b_i \le m$)가 주어진다. 이는 $i$번째 직원이 출근하고 퇴근하는 시각이다.

알렉스가 아예 출근하지 않아도 되는 경우에는 "-1 -1"을 출력한다.

그렇지 않은 경우에는 두 정수 $x$와 $y$ ($0 \le x < y \le m$, $y - x \le k$)를 출력한다. 이는 알렉스가 출근해야 하는 시각과 퇴근해야 하는 시각이며, 동료 중 누구도 불평하지 않고 근무 시간이 최소가 되는 값이다.

가능한 해가 여러 개이면 그중 아무거나 출력해도 된다.