Поиск

Башни


Ограничение времени - 1 секунда

Ввод - стандартный ввод или input.txt

Ограничение памяти - 256Mb

Вывод - стандартный вывод или output.txt

Вася и Петя смотрели на башни, расставленные в клетках прямоугольной доски $$$m$$$ на $$$n$$$. Мальчики сидели с разных сторон одного угла и записали на какой высоте они видят каждый со своей стороны крышу здания.

Помогите понять возможно ли такое, и если возможно, то какое минимальное количество башен должно быть расположено на доске.

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

Первая строка ввода содержит одно число $$$n (1 \le n \le 10^5)$$$ — ширина вида Пети, следующая строка содержит $$$n$$$ натуральный чисел — высоты башен со стороны Пети.

Третья строка ввода содержит одно число $$$m (1 \le m \le 10^5)$$$ — ширина вида Васи, следующая строка содержит $$$m$$$ натуральных чисел —- высоты башен со стороны Васи.

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

Вывести одно целое число — минимальное количество башен. Если получить заданные виды невозможно, то вывести сообщение NO.

Примеры

Входные данные
3
1 6 4
4
6 3 1 2
Выходные данные
5
Входные данные
2
1 1
2
5 5
Выходные данные
NO

Примечание

Такое возможное расположение в примере.

$$$\begin{array}{|l|l|l|} \hline & 6 & 4 \\ \hline & 3 & \\ \hline 1 & & \\ \hline & 2 & \\ \hline \end{array}$$$

Башни

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

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

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


Для отправки решения задачи необходимо авторизоваться!