iktk   2년 전

문제

그린델왈드는 마법부를 장악하기 위해 $n$명의 스파이를 고용했다. 스파이들은 $1$부터 $n$까지 서로 다른 정수 번호를 가지고 있으며, 그린델왈드의 계획에 따라 $i$번 스파이는 마법부 건물 $f_i$층에 침입해야 한다.

스파이들은 맨 처음에 다같이 엘리베이터를 탄다. 그러나, 키가 작아서 자기가 침투해야 할 층의 버튼을 누르지 못하는 스파이들도 있다. 엘리베이터의 버튼은 한 줄로 되어 있으며 $1$층으로 가는 버튼은 높이 $h$에, $2$층으로 가는 버튼은 높이 $h+1$에, $\cdots$ $k$층으로 가는 버튼은 높이 $h+k-1$에 있다. $i$번 스파이의 키는 $g_i$이며, 버튼의 높이가 자신의 키가 어떤 버튼의 높이보다 작지 않아야 버튼을 누를 수 있다.

만약 스파이가 엘리베이터로 자신이 침투해야 할 층에 도착하지 못한다면, 계단을 이용할 수 있다. 스파이들에게 혼동을 주지 않기 위해서, 그린델왈드는 스파이들이 자신이 침투해야 할 층에 도착하는 즉시 엘리베이터에서 내리라고 지시하였다.

침투 절차는 다음과 같다. 맨 처음에 엘리베티어 문이 열리고, 스파이들이 다같이 1층에서 엘리베이터를 타고 엘리베이터 문이 닫힌다. 엘리베이터에 있는 스파이들 중 한 사람이 버튼을 누르고, 해당하는 층으로 엘리베이터가 이동한다. 엘리베이터 문이 열리고, 해당 층에 침투해야 하는 스파이들이 모두 내리고 엘리베이터 문이 닫힌다. 그 후에 엘리베이터에 남아있는 스파이들 중 한 사람이 버튼을 누르고, 절차가 계속된다. 누구나 누를 수 있는 높이에 열림 버튼도 있어서, 현재 층에서 내리는 것은 언제나 가능하다.

만약 어떤 스파이가 침투해야 할 층을 지나치게 되면 그 스파이는 패닉에 빠지므로, 그렇게 해서는 안된다. 엘리베이터 버튼은 문이 닫힌 동안 하나만 누를 수 있다.

침투는 은밀하게 진행해야 하기 때문에 그린델왈드의 목표는 스파이들이 계단으로 오르는 층수를 최소화하는 것이다. 이 값을 구해보자.

입력

표준입력의 첫 번째 줄에 문제에 언급된 두 정수 $n(1\le n\le 100\,000)$, $h(1\le h\le 10^9)$가 주어진다.

두 번째 줄부터 $n$줄에 걸쳐 각 스파이의 정보가 $g_i\quad f_i$ 형식으로 주어진다. ($1\le g_i , f_i\le 10^9$)

출력

각 스파이가 계단을 이용해야 하는 층수의 합의 최솟값을 구하여 출력한다.

댓글을 작성하려면 로그인해야 합니다.