아케이드
시간 제한1초메모리 제한1024 MB
누르는 시각과 버튼이 주어질 때, 손 하나가 초당 한 칸씩 움직일 수 있다면 모든 입력을 처리하는 데 필요한 손의 최소 개수를 구한다.
문제
외계 문어 Emily는 아케이드 게임을 하고 있다. 게임기는 N개의 버튼으로 이루어져 있고, 버튼은 왼쪽에서 오른쪽으로 1번부터 N번까지 번호가 붙어 있다. 게임은 1초에 하나씩, 모두 M개의 버튼을 누르는 방식으로 진행된다. 게임 시작 후 Ti초가 되는 시점에 버튼 Ai를 눌러야 한다. i ≠ j인데 Ti = Tj이고 Ai = Aj인 경우도 있을 수 있다.
Emily의 손은 각각 게임 시작 시 임의의 위치에서 출발할 수 있고, 손 하나를 버튼에서 인접한 버튼으로 옮기는 데 정확히 1초가 걸린다. Emily의 손은 동시에 움직일 수 있으며, 버튼을 누르는 데는 시간이 걸리지 않는다. 외계 문어는 손이 무한히 많으므로 M개의 버튼을 모두 눌러 항상 최고 점수를 얻을 수 있다. 그러나 Emily는 게으르기 때문에 손을 전부 쓰고 싶어 하지 않는다. 최고 점수를 얻는 데 필요한 최소 손의 수를 S라고 하자.
Emily가 수행해야 하는 버튼 입력이 정확히 주어질 때, 게임에서 최고 점수를 얻기 위해 필요한 최소 손의 수를 구하자. S의 값을 구해 Emily에게 알려주자.
입력
프로그램은 표준 입력에서 입력을 받는다.
첫째 줄에는 두 정수 N과 M이 주어진다.
둘째 줄에는 M개의 정수가 주어지며, i번째 정수는 Ti를 나타낸다.
셋째 줄에는 M개의 정수가 주어지며, i번째 정수는 Ai를 나타낸다.
출력
프로그램은 표준 출력에 출력을 해야 한다.
출력은 한 줄에 하나의 정수여야 하며, 이는 Emily가 게임에서 최고 점수를 얻기 위해 필요한 최소 손의 수이다.
제한
- 1 ≤ N ≤ 10^9
- 1 ≤ M ≤ 5 × 10^5
- 1 ≤ Ai ≤ N
- 1 ≤ Ti ≤ 10^9