계단

배찌는 $1$ 층부터 $M$ 층까지 있는 건물의 $F$ 층에 살고 있다. 배찌는 이 건물에 있는 계단을 이용해서 운동을 하고 싶다. 배찌는 각 층에서 다음과 같은 일 중 하나를 골라서 하나를 진행한다.

1. 현재 배찌가 있는 곳이 $X$ 층이고 $X < M$ 이면, 계단을 한 층 올라 $X+1$ 층으로 갈 수 있다.
2. 현재 배찌가 있는 위치와 관계 없이, 엘리베이터를 타고 원하는 층으로 움직일 수 있다.

배찌는 자기가 살고 있는 $F$ 층에서 출발해서, 계단을 한 층 오르는 것을 총 $N$ 번 하고 다시 자기가 살고 있는 $F$ 층으로 돌아오고 싶어한다. 그 과정에서 엘리베이터를 타는 것은 언제든 할 수 있다. 운동을 마치기 위해 배찌가 엘리베이터를 타야 하는 횟수의 최솟값을 구하여라.

입력 형식

첫 줄에 건물의 총 층수 $M$, 배찌가 사는 층수 $F$, 배찌가 오르고 싶은 계단의 총 층수 $N$이 공백으로 구분되어 주어진다. ($2\le M \le 1\, 000\,000\,000;$ $1 \le F \le M;$ $1 \le N \le 1\,000\,000\,000$)

출력 형식

첫 줄에 배찌가 엘리베이터를 타야 하는 횟수의 최솟값을 출력한다.

입력 예제

10 8 34

출력 예제

4

예제 설명

엘리베이터를 $4$ 번 타면서 운동을 마치는 방법 중 하나는 다음과 같다.

• 처음에 엘리베이터를 타고 $1$층으로 간다. (엘리베이터 $1$회)
• 계단을 올라서 $10$층까지 간 후 엘리베이터를 타고 $1$층으로 가는 것을, $3$ 번 반복한다. (한 층 오르기 $27$회, 엘리베이터 $3$회)
• 계단을 올라서 $8$층에 도착하고 운동이 끝난다. (한 층 오르기 $7$회)

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

• 종류 1 (36점): $N \le 100;$ $M \le 100$
• 종류 2 (64점): 추가적인 제한 조건이 없음.

해설

펼치기