cho.sh

Horror Film Night

Given the sets of days each of two people likes films on, find the longest subsequence with no two consecutive films disliked by the same person.

Medium7GreedyTwo pointersDynamic programmingNo attempts yetTime limit2sMemory limit512 MB

Problem

Emma and Marcos are two friends who love horror films. This year, and in the years after it, they want to watch as many films together as possible. Their taste is not the same, so every now and then one of them has to sit through a film she or he dislikes. A film that neither of them likes, they skip. To keep things fair they agreed on one rule: they never watch two films in a row that the same person dislikes. So if one of them dislikes the film they are watching now, that person likes the next film they watch. Two films are in a row when they are neighbours in the sequence of films actually watched, and their days do not have to be next to each other.

They open the TV guide and mark the films they like. There is one channel, it shows one film per day, and the guide is already fixed for the next 1000000 days.

Find the largest number of films they can watch under this rule.

Input

The input consists of two lines, one for each person. Each line has the following form:

  • one integer kk (0≤k≤10000000 \le k \le 1000000), the number of films this person likes;
  • followed by kk integers, the days with a film this person likes. The days are numbered 0 to 999999.

Output

Print one line with one integer, the largest number of films they can watch together under the rule.