Under construction

Still being built. Things may change

Rhythm Flow

Interview

Time limit1sMemory limit1024 MB

Summary
Match expected and actual presses in order, each at most once, to maximize the total points, where each pair scores 7, 6, 4, 2, or 0 based on the time gap.
Level

Medium5 of 10

Topics
Dynamic programming, Array
Solved
No attempts yet

Problem

You are designing a scoring algorithm for the new hit rhythm game Rhythm Flow, where players must press a button in time with the music. During a round, there are points in time when a visual indicator flashes on the screen. Players are expected to press the button at those times, and only at those times. Human reaction time is not instantaneous, so the game accepts a press a few milliseconds earlier or later than expected. More accurate presses are worth more points.

The following table lists how many points a player gets depending on how far the actual press is from the expected press, in milliseconds:

Time Difference (ms)Points
[0,15][0,15]7
(15,23](15,23]6
(23,43](23,43]4
(43,102](43,102]2

Presses with a difference of 103103 milliseconds or more score no points.

During gameplay, the player presses the button some number of times. Each actual press is matched with at most one expected press, with this restriction: if one actual press happens before another actual press and both are matched, then the expected press matched to the first must be strictly before the expected press matched to the second.

You want the matching that maximizes the total points. Compute the final score of the round under this matching.

Input

The first line contains two integers nn and mm (1≤n,m≤20001 \le n, m \le 2000), where nn is the number of expected button presses and mm is the number of actual button presses.

Each of the next nn lines contains a single integer ee (1≤e≤1091 \le e \le 10^9), the times of the expected button presses in milliseconds from the start of the round. These values are unique and sorted in increasing order.

Each of the next mm lines contains a single integer aa (1≤a≤1091 \le a \le 10^9), the times of the actual button presses in milliseconds from the start of the round. These values are unique and sorted in increasing order.

Output

Output a single integer: the total number of points the player earns under a maximally generous scoring engine.

Examples3

  1. Example 1

    Input
    3 4
    100
    200
    300
    99
    201
    240
    323
    
    Expected output
    20
    
  2. Example 2

    Input
    4 3
    1000
    2000
    2500
    3000
    1103
    2598
    4000
    
    Expected output
    2
    
  3. Example 3

    Input
    2 2
    100
    144
    56
    100
    
    Expected output
    7