리듬 플로우
면접 대비시간 제한1초메모리 제한1024 MB
예상 입력과 실제 입력을 순서를 지켜 최대 한 번씩 짝지어, 시간 차이에 따른 점수 합의 최댓값을 구합니다.
문제
음악에 맞춰 제때 버튼을 누르는 새 리듬 게임 Rhythm Flow의 채점 알고리즘을 설계하고 있습니다. 한 라운드 동안 화면에 시각적 표시가 깜빡이는 시점이 있습니다. 플레이어는 그 시점에만 버튼을 누르도록 기대됩니다. 사람의 반응 시간은 순간적이지 않으므로, 게임은 기대된 시점보다 몇 밀리초 일찍 또는 늦게 누른 입력도 인정합니다. 더 정확하게 누를수록 점수가 높습니다.
다음 표는 실제 입력 시각이 기대된 입력 시각에서 얼마나 떨어져 있는지에 따라 플레이어가 얻는 점수를 밀리초 단위로 정리한 것입니다.
차이가 밀리초 이상인 입력은 점수를 얻지 못합니다.
게임 중 플레이어는 버튼을 여러 번 누릅니다. 각 실제 입력은 기대된 입력 중 최대 하나와 짝지어집니다. 단, 제약이 있습니다. 실제 입력 A가 실제 입력 B보다 먼저 일어나고 두 입력이 모두 짝지어졌다면, A와 짝지어진 기대 입력은 B와 짝지어진 기대 입력보다 엄격하게 앞서야 합니다.
총 점수가 최대가 되는 짝짓기를 골라 그 짝짓기에서의 라운드 최종 점수를 구하세요.
입력
첫 번째 줄에 두 정수 과 ()이 주어집니다. 은 기대된 버튼 입력의 개수이고, 은 실제 버튼 입력의 개수입니다.
다음 개 줄에는 각각 정수 () 하나가 주어집니다. 라운드 시작부터 기대된 버튼 입력 시각을 밀리초 단위로 나타냅니다. 값은 서로 다르며 오름차순으로 정렬되어 있습니다.
다음 개 줄에는 각각 정수 () 하나가 주어집니다. 라운드 시작부터 실제 버튼 입력 시각을 밀리초 단위로 나타냅니다. 값은 서로 다르며 오름차순으로 정렬되어 있습니다.
출력
최대한 관대한 채점 엔진에서 플레이어가 얻는 총 점수를 나타내는 정수 하나를 출력하세요.