만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

리듬 플로우

면접 대비

시간 제한1초메모리 제한1024 MB

요약
예상 입력과 실제 입력을 순서를 지켜 최대 한 번씩 짝지어, 시간 차이에 따른 점수 합의 최댓값을 구합니다.
난이도

보통10점 중 5점

유형
동적 계획법, 배열
정답자
아직 제출이 없습니다

문제

음악에 맞춰 제때 버튼을 누르는 새 리듬 게임 Rhythm Flow의 채점 알고리즘을 설계하고 있습니다. 한 라운드 동안 화면에 시각적 표시가 깜빡이는 시점이 있습니다. 플레이어는 그 시점에만 버튼을 누르도록 기대됩니다. 사람의 반응 시간은 순간적이지 않으므로, 게임은 기대된 시점보다 몇 밀리초 일찍 또는 늦게 누른 입력도 인정합니다. 더 정확하게 누를수록 점수가 높습니다.

다음 표는 실제 입력 시각이 기대된 입력 시각에서 얼마나 떨어져 있는지에 따라 플레이어가 얻는 점수를 밀리초 단위로 정리한 것입니다.

시간 차이 (ms)점수
[0,15][0,15]7
(15,23](15,23]6
(23,43](23,43]4
(43,102](43,102]2

차이가 103103밀리초 이상인 입력은 점수를 얻지 못합니다.

게임 중 플레이어는 버튼을 여러 번 누릅니다. 각 실제 입력은 기대된 입력 중 최대 하나와 짝지어집니다. 단, 제약이 있습니다. 실제 입력 A가 실제 입력 B보다 먼저 일어나고 두 입력이 모두 짝지어졌다면, A와 짝지어진 기대 입력은 B와 짝지어진 기대 입력보다 엄격하게 앞서야 합니다.

총 점수가 최대가 되는 짝짓기를 골라 그 짝짓기에서의 라운드 최종 점수를 구하세요.

입력

첫 번째 줄에 두 정수 nn과 mm (1≤n,m≤20001 \le n, m \le 2000)이 주어집니다. nn은 기대된 버튼 입력의 개수이고, mm은 실제 버튼 입력의 개수입니다.

다음 nn개 줄에는 각각 정수 ee (1≤e≤1091 \le e \le 10^9) 하나가 주어집니다. 라운드 시작부터 기대된 버튼 입력 시각을 밀리초 단위로 나타냅니다. 값은 서로 다르며 오름차순으로 정렬되어 있습니다.

다음 mm개 줄에는 각각 정수 aa (1≤a≤1091 \le a \le 10^9) 하나가 주어집니다. 라운드 시작부터 실제 버튼 입력 시각을 밀리초 단위로 나타냅니다. 값은 서로 다르며 오름차순으로 정렬되어 있습니다.

출력

최대한 관대한 채점 엔진에서 플레이어가 얻는 총 점수를 나타내는 정수 하나를 출력하세요.

예제3

  1. 예제 1

    입력
    3 4
    100
    200
    300
    99
    201
    240
    323
    
    예상 출력
    20
    
  2. 예제 2

    입력
    4 3
    1000
    2000
    2500
    3000
    1103
    2598
    4000
    
    예상 출력
    2
    
  3. 예제 3

    입력
    2 2
    100
    144
    56
    100
    
    예상 출력
    7