문제
JOI 군은 숫자 키패드를 하나 가지고 있다. 이 키패드에는 0부터 9까지의 숫자가 다음 그림과 같은 형태로 배치되어 있다.
또한, 숫자 2와 숫자 3 아래에는 키가 존재하지 않음을 유의하라.
키패드에는 현재 특정 키를 가리키는 커서(cursor)가 존재하며, 처음에는 0이 적힌 키를 가리키고 있다.
JOI 군은 한 번의 연산(조작)으로 다음 중 하나를 수행할 수 있다.
커서를 이동
현재 커서가 가리키고 있는 키에서 상하좌우로 인접한 키로 이동할 수 있다.
단, 키가 존재하지 않는 위치로는 이동할 수 없다.
키를 누르기
커서가 가리키는 키를 입력한다.
입력된 숫자가 이미 있을 경우, 기존 숫자의 오른쪽에 추가된다.
이제 JOI 군은 이 키패드를 사용하여,
텐키 조작에는 시간이 걸리므로, 가장 적은 조작 횟수로 입력하고자 한다.
입력
첫 줄에 두 정수
2≤M≤100,000 1≤R<M
출력
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 50점 | |
| #2 | 50점 | 추가 제약 조건 없음 |
예제1
10000013 5
다음 5번의 조작을 통해 13을 입력할 수 있다.
이보다 적은 조작으로 조건을 만족하는 정수를 입력할 방법은 없으므로, 최소 횟수는 5이다.
커서를 위로 이동 → 커서가 1을 가리킨다.
키를 누름 → 1이 입력된다.
커서를 오른쪽으로 이동 → 2를 가리킨다.
커서를 오른쪽으로 이동 → 3을 가리킨다.
키를 누름 → 3이 입력되어 13이 완성된다.
예제2
43 3
3번의 조작을 통해 11을 입력할 수 있다.
3을 직접 입력하려면 4번 이상의 조작이 필요하므로, 최적해는 11이다.
커서를 위로 이동 → 1을 가리킨다.
키를 누름 → 1이 입력된다.
키를 다시 누름 → 1이 입력되어 11이 완성된다.