Background

The river porpoise stands amid splashing waves, and the shore bird leisurely catches fish.

Problem Description

A bird is flying among $n$ trees. The height of the $i$-th tree is $a_i$, arranged from left to right. This bird is too heavy to fly upward, so it can only glide to the left or to the right.

If the bird is currently standing on a tree of height $a_i$, then the height of the tree it can fly to must be less than $a_i$, and the heights of all trees it passes over during the flight must also be less than $a_i$.

The bird has $k$ teleport cards. The magic value of the $i$-th card is $b_i$. The bird may choose to use a teleport card on any tree, teleporting to a tree whose height is not greater than the magic value of that card (if the height of the tree where the bird currently is is not greater than the card’s magic value, then it may teleport to the current tree). However, it can only use the teleport cards in the given order. The testdata guarantees that all teleport cards can be used (that is, there is no teleport card whose magic value is less than the heights of all trees).

The bird starts at the first tree. Please compute the maximum number of flights it can make (teleports are not counted).

Note: The bird may pass through the same tree multiple times.

Input Format

The first line contains two integers $n, k$, representing the number of trees and the number of teleport cards.

The next line contains $n$ integers, representing the height of each tree.

The next line contains $k$ integers, representing the magic value of each teleport card, given in the order they are used.

Output Format

Output one line with one integer, representing the maximum number of flights the bird can make.

3 1
1 5 2
6

1

5 2
1 3 2 7 1
4 10

3

Hint

For $10\%$ of the data, $1 \le n, k \le 10$.

For $30\%$ of the data, $1 \le n, k \le 5 \times 10^3$.

For $70\%$ of the data, $1 \le n, k \le 10^5$.

For $100\%$ of the data, $1 \le n, k \le 3 \times 10^5$, $0 \le a_i, b_i \le 10^9$.

Translated by ChatGPT 5