울타리

톰 소여는 울타리를 칠하는 중요한 일을 맡았다. 울타리는 n개의 널빤지로 이루어져 있다. 예전에 칠한 적이 있지만, 울타리의 일부 구간에서 페인트가 벗겨졌다. 톰은 바로 이 널빤지들을 칠해야 한다. 울타리가 크기 때문에, 울타리 옆으로 페인트가 가득 든 탱크차 한 대를 끌고 와야 했다. 탱크차는 울타리 끝에 놓였고 움직일 수 없다. 톰에게는 작은 양동이가 하나 있는데, 여기에 페인트를 담으면 울타리의 널빤지 k개를 칠할 수 있다. 톰은 언제든지 탱크차로 페인트를 다시 받으러 돌아갈 수 있다.

처음에 톰은 탱크차 옆에 있다. 이웃한 널빤지 사이의 거리는 1피트이고, 탱크차는 첫 번째 널빤지에서 1피트 떨어져 있다. 일을 마친 톰은 붓과 양동이를 탱크차 옆의 원래 위치에 놓아야 한다.

울타리를 칠하기 위해 톰이 걸어야 하는 최소 거리를 구해야 한다.

입력 파일의 첫째 줄에는 울타리의 널빤지 수 n (1 ≤ n ≤ 10^9)과 양동이의 용량 k (1 ≤ k ≤ 100)가 주어진다. 둘째 줄에는 칠하지 않은 울타리 구간의 수 m (1 ≤ m ≤ 50)이 주어진다. 이어서 m개의 줄이 주어지고, 각 줄에 칠하지 않은 구간 하나가 설명된다. 구간은 왼쪽 경계 li와 오른쪽 경계 ri (1 ≤ li ≤ ri ≤ n)로 설명된다. 이 설명은 울타리의 li번째, (li+1)번째, …, (ri–1)번째, ri번째 널빤지가 칠해지지 않았음을 뜻한다 (널빤지는 1부터 n까지 번호가 매겨진다). 입력 파일에 주어지는 칠하지 않은 구간들은 서로 겹치지 않음이 보장된다.

톰이 중요한 임무를 수행하기 위해 걸어야 하는 최소 거리를 피트 단위로 나타내는 수 하나를 출력한다.