Under construction

Still being built. Things may change

Frosh Week

Interview

Time limit4sMemory limit512 MB

Summary
Given task durations and quiet-interval lengths, each between 100000 and 199999, pair tasks with intervals that fit them and maximize the number of completed tasks.
Level

Medium4 of 10

Topics
Greedy, Two pointers, Sorting, Array
Solved
No attempts yet

Problem

Professor Zac wants to finish a pile of tasks during the first week of the term. He knows exactly how long each task takes, down to the millisecond. The same week is also frosh week. Zac's office window looks straight out at the stage where loud music is played, and he cannot concentrate on any task while the music is on.

The event organizers keep precise time too. They give Zac the intervals when no music is playing, specified by their start and end times down to the millisecond.

Every task Zac finishes must start and end inside a single quiet interval. He cannot pause a task when the music comes back, because he loses his train of thought. The task lengths and the quiet interval lengths fall in a range that makes finishing two or more tasks in one quiet interval impossible anyway.

Given the time tit_i (in milliseconds) that each task takes and the length ℓj\ell_j (in milliseconds) of each interval with no music, find the largest number of tasks Zac can finish.

Input

The first line contains two integers nn and mm separated by a space, where nn is the number of tasks and mm is the number of intervals with no music.

The second line contains the times t1,t2,…,tnt_1, t_2, \dots, t_n that the tasks take.

The third line contains the lengths ℓ1,ℓ2,…,ℓm\ell_1, \ell_2, \dots, \ell_m of the quiet intervals Zac has at work this week.

You may assume 1≤n,m≤200 0001 \le n, m \le 200\,000 and 100 000≤ti,ℓj≤199 999100\,000 \le t_i, \ell_j \le 199\,999 for every task ii and every quiet interval jj.

Output

Print one line with the number of tasks Zac can finish during this first week.

Examples3

  1. Example 1

    Input
    5 4
    150000 100000 160000 100000 180000
    190000 170000 140000 160000
    
    Expected output
    4
    
  2. Example 2

    Input
    4 4
    180000 185000 199999 100000
    199999 180000 170000 120000
    
    Expected output
    3
    
  3. Example 3

    Input
    3 3
    199999 180000 170001
    199999 170000 180000
    
    Expected output
    2