/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君のクラスでは M 日間の合宿が予定されています。合宿の各日にはおやつの予算が決まっており、日 j （ 1 \leq j \leq M ）のおやつ予算は S_j 円です。
合宿に持っていくおやつは、お店に並んでいる N 種類の商品の中から 1 種類だけ選び、合宿期間中は毎日そのおやつを 1 つずつ購入して食べることになります。商品 i の価格は R_i 円です。
高橋君は、すべての日においておやつの価格が予算以下であるような商品を選びたいです。すなわち、すべての日 j について R_i \leq S_j が成り立つような商品 i を選びたいです。
このような条件を満たす商品の数を求めてください。
制約
- 1 \leq N \leq 10^6
- 1 \leq M \leq 10^6
- 1 \leq R_i \leq 10^9 （ 1 \leq i \leq N ）
- 1 \leq S_j \leq 10^9 （ 1 \leq j \leq M ）
- 入力はすべて整数である
入力
N M R_1 R_2 \ldots R_N S_1 S_2 \ldots S_M
- 1 行目には、商品の種類数を表す N と、合宿の日数を表す M が、スペース区切りで与えられる。
- 2 行目には、各商品の価格を表す R_1, R_2, \ldots, R_N が、スペース区切りで与えられる。
- 3 行目には、各日のおやつ予算を表す S_1, S_2, \ldots, S_M が、スペース区切りで与えられる。
出力
条件を満たす商品の数を 1 行で出力してください。
入力例 1
5 3 100 200 300 400 500 350 300 450
出力例 1
3
入力例 2
3 4 100 200 300 50 60 70 80
出力例 2
0
入力例 3
12 8 120 500 450 300 800 450 100 700 600 250 449 451 1000 900 450 800 700 600 500 550
出力例 3
7
入力例 4
30 20 1500 999 1000 1001 750 2000 50 300 1200 980 1100 1020 999 100 5000 250 875 1000 1 450 650 700 800 900 10000 1050 990 995 996 997 2000 1500 1200 1100 1050 1000 1300 1400 1600 1700 1800 1900 1250 1150 1080 1020 1010 1005 1000 3000
出力例 4
21
入力例 5
1 1 1000000000 1000000000
出力例 5
1
Score : 300 pts
Problem Statement
Takahashi's class has a training camp planned for M days. Each day of the camp has a fixed snack budget, and the snack budget for day j (1 \leq j \leq M) is S_j yen.
For the snacks to bring to the camp, he must choose exactly 1 type of product from the N types of products available at the store, and during the camp he will purchase and eat one of that snack each day. The price of product i is R_i yen.
Takahashi wants to choose a product such that the price of the snack is within the budget on every day. In other words, he wants to choose a product i such that R_i \leq S_j holds for every day j.
Find the number of products that satisfy this condition.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq M \leq 10^6
- 1 \leq R_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq S_j \leq 10^9 (1 \leq j \leq M)
- All input values are integers
Input
N M R_1 R_2 \ldots R_N S_1 S_2 \ldots S_M
- The first line contains N, the number of product types, and M, the number of days of the camp, separated by a space.
- The second line contains the prices of each product R_1, R_2, \ldots, R_N, separated by spaces.
- The third line contains the snack budget for each day S_1, S_2, \ldots, S_M, separated by spaces.
Output
Print the number of products that satisfy the condition on a single line.
Sample Input 1
5 3 100 200 300 400 500 350 300 450
Sample Output 1
3
Sample Input 2
3 4 100 200 300 50 60 70 80
Sample Output 2
0
Sample Input 3
12 8 120 500 450 300 800 450 100 700 600 250 449 451 1000 900 450 800 700 600 500 550
Sample Output 3
7
Sample Input 4
30 20 1500 999 1000 1001 750 2000 50 300 1200 980 1100 1020 999 100 5000 250 875 1000 1 450 650 700 800 900 10000 1050 990 995 996 997 2000 1500 1200 1100 1050 1000 1300 1400 1600 1700 1800 1900 1250 1150 1080 1020 1010 1005 1000 3000
Sample Output 4
21
Sample Input 5
1 1 1000000000 1000000000
Sample Output 5
1