Under construction

Still being built. Things may change

Cupid of Love

Interview

Time limit1sMemory limit512 MB

Summary
Given heights and height thresholds for female and male students, find the maximum number of pairs where each partner prefers the other.
Level

Medium4 of 10

Topics
Graph, DFS
Solved
No attempts yet

Problem

Bosun came to Jinju for an outing and was so thirsty that he walked into a cafe in front of Gyeongsang National University. At that cafe, NN female students from Jinju National University of Education and MM male students from Yeonam College of Engineering were holding a group meeting.

This meeting has one curious fact. Each student's preference toward a partner depends on only one factor, height. Specifically, a female student prefers only male students shorter than her preference threshold. A male student prefers only female students taller than his preference threshold.

Jaehyeok, a self-proclaimed love cupid, was also in the cafe. He listened closely to the conversations at the meeting tables and learned the preference threshold of every student. Hoping that many couples would form, he decided to pair the students himself.

Watching all of this, Bosun wondered about the maximum number of couples that could form at this meeting. In this problem, a couple is a set of one female student and one male student who prefer each other, and no student can belong to more than one couple.

Input

The first line contains the number of female students NN and the number of male students MM, separated by a space. (1≤N,M≤4001 \le N, M \le 400)

The second line contains G1,…,GNG_1, \dots, G_N, separated by spaces. GiG_i is the height of the ii-th female student. (1≤Gi≤3001 \le G_i \le 300)

The third line contains B1,…,BMB_1, \dots, B_M, separated by spaces. BiB_i is the height of the ii-th male student. (1≤Bi≤3001 \le B_i \le 300)

The fourth line contains L1,…,LNL_1, \dots, L_N, separated by spaces. LiL_i is the preference threshold of the ii-th female student. (1≤Li≤3001 \le L_i \le 300)

The fifth line contains U1,…,UMU_1, \dots, U_M, separated by spaces. UiU_i is the preference threshold of the ii-th male student. (1≤Ui≤3001 \le U_i \le 300)

All numbers in the input are integers.

Output

On the first line, print the maximum number of couples that can form at the meeting.

Examples1

  1. Example 1

    Input
    2 2
    168 164
    179 183
    180 190
    155 165
    
    Expected output
    1