Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача B. Сочетания

Задачу добавил: alef

Успешно сдано решений: 16

Добрался доверенный человек до мастера зеркальных дел и рассказал ему мастер, что непростое это зеркало, волшебное. Если зеркало направить на солнце, а отраженный от него свет на белую стену — то можно увидеть на стене очертания другого города. А если не стена это будет, а дверь, и она будет полностью освещена отраженным светом, то, открыв дверь, можно попасть в этот город.

Когда узнал об этом царь Гордей, то повелел он все двери в палатах для ожидания посланников завесить коврами — только вход в палаты царские да выход на крыльцо оставить. Дверь будет считаться завешенной, если ковер закрывает ее полностью. Надежно закрепить ковер можно только при условии, что его стороны параллельны сторонам двери.

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

Все ковры и двери строго прямоугольной формы.


Формат входного файла input.txt

Первая строка — целые числа N и M (1 N, M 100000) — количество дверей, которые надо завесить, и количество имеющихся в распоряжении ковров.

Вторая строка — N целых чисел через пробел. Каждое число обозначает ширину очередной двери. Известно, что для всех дверей ширина соотносится с высотой в пропорции 1 : 2

Третья строка — 2*M целых чисел через пробел. Каждая пара чисел обозначает линейные размеры очередного ковра.

Линейные размеры дверей и ковров не превосходят 10000.


Формат выходного файла output.txt

Первая строка — целое число, максимально возможное количество дверей, которое удастся завесить имеющимися в наличии коврами


Пример входного файла

3 4

4 3 5

6 9 2 9 7 7 4 6


Пример выходного файла

2


Сдать задачу

Задать вопрос жюри по этой задаче