Максим хочет купить себе несколько игр в игровом магазине. Всего в магазине есть $$$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$$$-й банкноты из бумажника Максима.
Выведите одно целое число — количество игр, купленных Максимом.
5 4
2 4 5 2 4
5 3 4 6
3
5 2
20 40 50 20 40
19 20
0
6 4
4 8 15 16 23 42
1000 1000 1000 1000
4
Первый тестовый пример разобран в условии задачи.
Во втором тестовом примере Максим не может купить ни одну игру, потому что номинал первой банкноты в его бумажнике меньше, чем цена любой из игр в магазине.
В третьем тестовом примере номиналы банкнот в бумажнике Максима достаточно большие, чтобы покупать каждую встречающуюся игру до тех пор, пока у него не кончатся купюры.
Название |
---|