Алиса и Громозека играют в фишки-палочки. У каждого из них есть набор фишек, на каждой фишке записано одно целое число. Каждый из них выкладывает свои фишки вдоль двух параллельных горизонтальных линий. Следующим шагом Алиса соединяет палочкой две фишки, расположенные на разных горизонтальных линиях, то есть соединяет одну свою фишку с одной из фишек Громозеки по следующим правилам:
- числа, на фишке Алисы и на фишке Громозеки равны;
- соединяющая палочка не должна пересекать другие палочки;
- две палочки не могут указывать на одну и ту же фишку.
Далее, Громозека считает сколько палочек выложила Алиса. После этого, Алиса убирает свои палочки и фишки соединяет Громозека по тем же правилам. Выигрывает тот, кто выложит по данным правилам больше всего палочек.
Вас, как наблюдателя за этой игрой, просят определить максимальное количество палочек, которые можно выложить по указанным правилам.
Входные данные
Первая строка входных данных содержит число n - количество фишек Алисы. Вторая строка содержит n чисел nums1i - числа на фишках Алисы, в том порядке, в котором она их выложила. Третья строка содержит число m - количество фишек Громозеки. Четвертая строка содержит m чисел nums2j - числа на фишках Громозека, в том порядке, в котором он их выложил.
Ограничения
1 <= n, m <= 5001 <= nums1[i], nums2[j] <= 2000
Выходные данные
Выведите одно число - максимальное количество палочек, которые можно выложить по указанным в условии задачи правилам игры.
Примечание
Рисунок к первому тестовому примеру
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 4 2
3
1 2 4
|
2
|
|
2
|
5
2 5 1 2 5
6
10 5 2 1 5 2
|
3
|