구간 도약 최소 난이도 경로

일직선 상에 설치된 지점들 $1$부터 $N$까지가 있으며, 각 지점 $i$는 위치 $x_i$와 위험도 $d_i$를 가진다. 출발 지점 $1$에서 도착 지점 $N$까지 지점을 순서대로 선택해 이동하되, 연속한 선택 지점의 위치 차이는 항상 $L$ 이상 $U$ 이하이어야 한다. 선택한 모든 지점의 위험도 중 최댓값을 가능한 한 작게 만들고, 그 값이 같은 경우에는 선택한 지점의 수를 최소로 한다. 여러 경로가 그 둘을 모두 만족하면, 선택한 지점 인덱스 수열이 사전순으로 가장 앞선 것을 목표로 한다.

• 첫째 줄에 네 정수 $N$, $L$, $U$, $K$가 주어진다. $N$은 지점의 개수이며 $2 \le N \le 200000$, $L$과 $U$는 연속한 선택 지점 간 허용 거리 하한과 상한이며 $1 \le L \le U$, $K$는 선택 가능한 지점의 최대 개수 상한이며 $2 \le K \le N$이다.
• 이어서 $N$개의 줄에 걸쳐 각 줄마다 두 정수 $x_i$, $d_i$가 주어진다. $x_i$는 지점 $i$의 위치이며 $0 \le x_1 < x_2 < \cdots < x_N \le 10^9$를 만족한다. $d_i$는 지점 $i$의 위험도이며 $0 \le d_i \le 10^9$이다.
• 경로는 반드시 지점 $1$에서 시작하여 지점 $N$에서 끝나야 한다. 선택한 지점들의 인덱스 수열을 $i_1, i_2, \ldots, i_m$이라 할 때 $i_1 = 1$, $i_m = N$, $i_{t} < i_{t+1}$이며, 모든 $t$에 대해 $L \le x_{i_{t+1}} - x_{i_t} \le U$를 만족해야 한다.
• 선택한 지점의 개수 $m$은 $2 \le m \le K$를 만족해야 한다.
• 입력의 모든 정수는 10진수 표기로 주어진다.

• 유효한 경로가 존재하지 않으면 첫째 줄에 $-1$만 출력한다.
• 유효한 경로가 존재하면 첫째 줄에 두 정수 $R$, $m$을 출력한다. $R$은 선택된 지점들의 위험도 중 최댓값의 최소값이고, $m$은 그 값을 달성하는 경로들 중 선택한 지점의 개수의 최솟값이다.
• 둘째 줄에 해당 조건을 만족하는 경로의 지점 인덱스 $m$개를 $i_1, i_2, \ldots, i_m$ 순서로 출력한다. 인덱스들은 한 칸의 공백으로 구분한다.
• 여러 경로가 위 조건을 만족하면 사전순으로 가장 앞선 인덱스 수열을 출력한다.
• 수가 한 줄에 여러 개 주어지는 경우 각 수 사이를 공백 하나로 구분한다.