409551: GYM103630 C Рудольф и IQ ПФО

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Рудольф и IQ ПФОограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Одним весенним вечером Рудольф сидел и размышлял о том, кто он такой. Внезапно он понял, что он персонаж задач олимпиады «IQ ПФО».

Придя в себя спустя некоторое время Рудольф решил, что в таком случае не мешало бы украсить его комнату словами «IQ». Для этого он вырезал из бумаги $$$N$$$ палочек с длинами $$$L_i (1 \le i \le N)$$$, а также $$$M$$$ окружностей с радиусами $$$R_j (1 \le j \le M)$$$. Он решил составлять слова следующим образом: на букву «I» он потратит одну палочку, а на букву «Q» — одну палочку и одну окружность. Но не любые палочки будут гармонично смотреться с любыми окружностями. Некоторое время Рудольф составлял различные комбинации и в итоге выяснил два правила идеального слова:

  1. Длина палочки для буквы «I» должна быть равна диаметру окружности для буквы «Q».
  2. Длина палочки для буквы «Q» должна быть строго меньше радиуса окружности.
Идеальное слово

Теперь Рудольф задался вопросом, какое максимальное количество идеальных слов он может составить из имеющихся палочек и окружностей. Он просит вас помочь ему с этим вопросом.

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

Первая строка входных данных содержит два целых числа $$$N$$$ и $$$M$$$ $$$(1 \le N, M \le 10^5)$$$ — количество палочек и окружностей соответственно.

Вторая строка содержит $$$N$$$ целых чисел $$$L_i (1 \le L_i \le 10^9)$$$ — длины палочек.

Третья строка содержит $$$M$$$ целых чисел $$$R_i (1 \le R_i \le 10^9)$$$ — радиусы окружностей.

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

Выведите одно целое число — максимальное количество слов «IQ», которые может составить Рудольф.

ПримерВходные данные
5 3
10 6 8 1 2
6 5 3
Выходные данные
2
Примечание

В примере Рудольф может для первого слова взять палочки длиной $$$10$$$ и $$$1$$$ и окружность радиуса $$$5$$$, а для второго слова — палочки длиной $$$6$$$ и $$$2$$$ и окружность радиуса $$$3$$$. Также корректно будет взять палочки длиной $$$10$$$ и $$$2$$$ для первого слова, и палочки $$$6$$$ и $$$1$$$ для второго.

加入题单

上一题 下一题 算法标签: