프레임

Throughout Igor K.은 살아오면서 주목할 만한 많은 상황을 겪었다. 우리는 바이러스 이야기와 그의 수학 경력 이야기, 그리고 물론 그의 유명한 프로그래밍 업적을 기억한다. 하지만 사람이 항상 새로운 취미를 갖기만 하는 것은 아니며, 무언가를 그만둘 수도 있다.

이번에는 Igor K.이 자신의 취미 중 하나인 동영상 편집과 더빙에 실망했다. 게다가 너무나 크게 실망한 나머지, 자신의 비밀 자료를 영원히 파기하기로 했다.

Igor K.은 파일과 폴더를 작은 아이콘으로 나타내는 Pindows XR 운영 체제를 사용한다. 이때 어떤 창에서든 가로 한 줄에 m개의 아이콘이 들어갈 수 있다.

Igor K.의 컴퓨터에는 D: 디스크의 루트 디렉터리에 n개의 폴더가 있다. 폴더에는 왼쪽에서 오른쪽으로, 위에서 아래로 순서대로 1부터 n까지 번호가 매겨져 있다(그림을 참고한다). 이때 비밀 동영상이 든 폴더의 번호는 a부터 b까지이며 양 끝을 포함한다. Igor K.은 가능한 한 적은 횟수로 프레임 선택을 한 다음 Shift+Delete를 정확히 한 번 눌러 이 폴더들을 영원히 삭제하려 한다. a부터 b까지의 폴더만 선택하기 위해 Igor K.이 폴더를 선택해야 하는 최소 횟수는 얼마인가? 이미 선택된 어떤 폴더를 다시 선택하면 그 폴더의 선택이 해제된다는 점에 유의한다. 각 선택 영역은 변이 화면의 테두리와 평행한 어떤 직사각형 모양이다.

유일한 줄에 네 정수 n, m, a, b (1 ≤ n, m ≤ 109, 1 ≤ a ≤ b ≤ n)가 주어진다. 이들은 각각 Igor K.의 컴퓨터에 있는 폴더의 수, 창의 너비, 삭제해야 하는 첫 폴더와 마지막 폴더의 번호이다.

프레임을 사용하여 a부터 b까지의 번호가 붙은 폴더만 선택하기 위해 Igor K.이 폴더를 선택해야 하는 최소 횟수를 하나의 수로 출력한다.

아래 그림은 문제의 테스트를 보여 준다.

첫 번째 테스트:

이 테스트에서는 첫 번째 선택으로 폴더 3과 4를 선택하고, 두 번째 선택으로 폴더 5, 6, 7, 8을 선택하며, 세 번째이자 마지막 선택으로 폴더 9를 선택할 수 있다.

두 번째 테스트:

이 테스트에서는 먼저 첫 번째 행의 모든 폴더(2, 3, 4, 5)를 선택한 다음, 나머지 모든 폴더를 선택할 수 있다.