Олимпиадный тренинг

Задача . A. Покупка игр


Задача

Темы: реализация *800

Максим хочет купить себе несколько игр в игровом магазине. Всего в магазине есть \(n\) игр, \(i\)-я игра стоит \(c_i\).

У Максима есть бумажник, который можно представить в виде массива целых чисел. В его бумажнике есть \(m\) купюр, номинал \(j\)-й купюры — \(a_j\).

Игры в магазине пронумерованы в порядке слева направо, Максим пытается купить каждую игру в этом порядке.

Когда Максим находится на позиции \(i\) в магазине, он берет первую купюру из его бумажника (если его бумажник пустой, то он просто сразу же переходит к следующей позиции) и пытается купить \(i\)-ю игру, используя эту банкноту. После попытки купить \(n\)-ю игру Максим покидает магазин.

Максим покупает \(i\)-ю игру тогда и только тогда, когда номинал первой банкноты (которую он достает) из его бумажника больше либо равен цене \(i\)-й игры. Если он успешно покупает \(i\)-ю игру, первая банкнота из его бумажника пропадает и следующая по счету становится первой. Иначе Максим возвращает первую банкноту в свой бумажник (эта банкнота остается первой) и переходит к следующей игре.

Например, для массива \(c = [2, 4, 5, 2, 4]\) и массива \(a = [5, 3, 4, 6]\) будет происходить следующее: Максим покупает первую игру, используя первую банкноту (ее номинал равен \(5\)), она пропадает, и вторая банкнота (ее номинал равен \(3\)) становится первой в бумажнике Максима. Затем Максим не покупает вторую игру, потому что \(c_2 > a_2\), то же самое происходит с третьей игрой, затем он покупает четвертую игру, используя банкноту с номиналом \(a_2\) (третья банкнота становится первой в бумажнике Максима), и покупает пятую игру, используя банкноту с номиналом \(a_3\).

Ваша задача — сообщить, сколько игр купит Максим.

Входные данные

Первая строка входных данных содержит два целых числа \(n\) и \(m\) (\(1 \le n, m \le 1000\)) — количество игр и количество банкнот в бумажнике Максима.

Вторая строка входных данных содержит \(n\) целых чисел \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le 1000\)), где \(c_i\) равно стоимости \(i\)-й игры.

Третья строка входных данных содержит \(m\) целых чисел \(a_1, a_2, \dots, a_m\) (\(1 \le a_j \le 1000\)), где \(a_j\) равно номиналу \(j\)-й банкноты из бумажника Максима.

Выходные данные

Выведите одно целое число — количество игр, купленных Максимом.

Примечание

Первый тестовый пример разобран в условии задачи.

Во втором тестовом примере Максим не может купить ни одну игру, потому что номинал первой банкноты в его бумажнике меньше, чем цена любой из игр в магазине.

В третьем тестовом примере номиналы банкнот в бумажнике Максима достаточно большие, чтобы покупать каждую встречающуюся игру до тех пор, пока у него не кончатся купюры.


Примеры
Входные данныеВыходные данные
1 5 4
2 4 5 2 4
5 3 4 6
3
2 5 2
20 40 50 20 40
19 20
0
3 6 4
4 8 15 16 23 42
1000 1000 1000 1000
4

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя