E - Shelving Books on a Bookshelf Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は図書館の司書として、N 冊の本を本棚に配架する作業を担当することになりました。

本棚には M 個の空きスペースが一列に並んでおり、左から順にスペース 1、スペース 2、\ldots、スペース M と番号が振られています。スペース j には「耐荷重」を表す整数値 C_j が設定されており、各スペースには最大 1 冊の本しか置くことができません。

本には 1 から N までの番号が付けられており、本 i には「重さ」を表す整数値 W_i が与えられています。

高橋君は、本 1、本 2、\ldots、本 N の順に、1 冊ずつ以下の手順で配架場所を決めていきます。

  • まだ本が置かれていないスペースのうち、耐荷重がその本の重さ以上（すなわち C_j \geq W_i）であるスペースを候補とする。
  • 候補が 1 つ以上存在する場合、その中で最も番号が小さいスペースにその本を置く。本を置いたスペースは使用済みとなり、以降の本の配架先としては選べなくなる。
  • 候補が存在しない場合、その本の配架を断念する。断念した本は本棚に置かれず、以降再検討されることもない。

すべての本について配架場所を検討し終わった後、本棚に置くことができた本の冊数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M
W_1 W_2 \ldots W_N
C_1 C_2 \ldots C_M
  • 1 行目には、本の冊数を表す N と、本棚のスペース数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各本の重さ W_1, W_2, \ldots, W_N が、スペース区切りで与えられる。
  • 3 行目には、各スペースの耐荷重 C_1, C_2, \ldots, C_M が、スペース区切りで与えられる。

出力

本棚に置くことができた本の冊数を 1 行で出力してください。

入力例 1

4 5
3 5 2 7
4 6 3 8 2

出力例 1

4

入力例 2

6 5
5 3 8 2 10 1
7 4 9 3 6

出力例 2

5

入力例 3

10 8
5 1 9 3 7 6 2 4 8 10
6 3 10 5 8 2 7 4

出力例 3

8

Score : 433 pts

Problem Statement

Takahashi, working as a librarian, has been assigned the task of shelving N books onto a bookshelf.

The bookshelf has M empty spaces arranged in a row, numbered from left to right as space 1, space 2, \ldots, space M. Each space j has an integer value C_j representing its "weight capacity," and each space can hold at most 1 book.

The books are numbered from 1 to N, and book i has an integer value W_i representing its "weight."

Takahashi determines the placement for each book one at a time, in the order book 1, book 2, \ldots, book N, using the following procedure:

  • Among the spaces that do not yet have a book placed on them, consider as candidates those whose weight capacity is at least the weight of the book (i.e., C_j \geq W_i).
  • If there is at least one candidate, place the book on the candidate space with the smallest number. The space where a book is placed becomes occupied and can no longer be selected for subsequent books.
  • If there are no candidates, give up on shelving that book. A book that is given up on is not placed on the bookshelf and is never reconsidered.

After considering the placement for all books, determine the number of books that were successfully placed on the bookshelf.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • All inputs are integers

Input

N M
W_1 W_2 \ldots W_N
C_1 C_2 \ldots C_M
  • The first line contains N, the number of books, and M, the number of spaces on the bookshelf, separated by a space.
  • The second line contains the weights of each book W_1, W_2, \ldots, W_N, separated by spaces.
  • The third line contains the weight capacities of each space C_1, C_2, \ldots, C_M, separated by spaces.

Output

Print the number of books that were successfully placed on the bookshelf, on a single line.

Sample Input 1

4 5
3 5 2 7
4 6 3 8 2

Sample Output 1

4

Sample Input 2

6 5
5 3 8 2 10 1
7 4 9 3 6

Sample Output 2

5

Sample Input 3

10 8
5 1 9 3 7 6 2 4 8 10
6 3 10 5 8 2 7 4

Sample Output 3

8