Problembeschreibung
Es gibt viele Karten, auf denen jeweils eine ganze Zahl von $1$ bis $1000$ steht. Anna und Bruno spielen mit diesen Karten das folgende Spiel.
Anna hat einen Stapel aus $A$ Karten und Bruno hat einen Stapel aus $B$ Karten. Anna wirft eine beliebige Anzahl von Karten ($0$ Karten sind ebenfalls erlaubt) aus ihren $A$ Karten ab, um einen neuen Stapel zu bilden. Bruno wirft einige Karten ($0$ Karten sind ebenfalls erlaubt) von ganz oben und einige Karten ($0$ Karten sind ebenfalls erlaubt) von ganz unten von seinem aus $B$ Karten bestehenden Stapel ab, um einen neuen Stapel zu bilden. Die verbleibenden Karten werden beim Abwerfen jedoch nicht umsortiert. Wenn die auf diese Weise gebildeten $2$ Stapel übereinstimmen, wird die Anzahl der in einem der Stapel enthaltenen Karten zur Punktzahl der $2$ Spieler. Hierbei stimmen $2$ Stapel überein, wenn die Anzahl der in jedem Stapel enthaltenen Karten $n$ gleich ist und für jede $i$-te Karte von oben ($1 \le i \le n$) die auf den Karten stehenden ganzen Zahlen jeweils gleich sind.
Nehmen wir zum Beispiel an, Anna hat einen Stapel aus $5$ Karten, auf denen von oben nach unten die ganzen Zahlen $1, 2, 3, 4, 5$ stehen, und Bruno hat einen Stapel aus $4$ Karten, auf denen von oben nach unten die ganzen Zahlen $3, 1, 4, 1$ stehen. Wenn Anna nun die Karten $2, 3, 5$ abwirft und Bruno die oberste Karte $3$ und die unterste Karte $1$ abwirft, stimmen die Stapel der $2$ Spieler überein. Da die Anzahl der in einem der verbleibenden Stapel enthaltenen Karten $2$ beträgt, erhalten die $2$ Spieler eine Punktzahl von $2$.
Wir wollen den maximalen Wert der Punktzahl der $2$ Spieler bestimmen.
Aufgabe
Gegeben sind die Informationen über die Kartenstapel von Anna und Bruno. Schreibe ein Programm, das den maximalen Wert der Punktzahl der $2$ Spieler bestimmt.
Beschränkungen
- $1 \le A \le 5000$: Die Anzahl der Karten in Annas Stapel.
- $1 \le B \le 5000$: Die Anzahl der Karten in Brunos Stapel.
- Die auf den Karten stehenden ganzen Zahlen liegen zwischen $1$ und $1000$ (einschließlich).
Eingabe
Lies die folgenden Daten von der Standardeingabe.
- In der $1$-ten Zeile stehen die ganzen Zahlen $A, B$, getrennt durch ein Leerzeichen.
- In der $2$-ten Zeile stehen $A$ ganze Zahlen, getrennt durch Leerzeichen; die $i$-te ganze Zahl ($1 \le i \le A$) gibt die ganze Zahl an, die auf der $i$-ten Karte von oben in Annas Stapel steht.
- In der $3$-ten Zeile stehen $B$ ganze Zahlen, getrennt durch Leerzeichen; die $j$-te ganze Zahl ($1 \le j \le B$) gibt die ganze Zahl an, die auf der $j$-ten Karte von oben in Brunos Stapel steht.
Ausgabe
Gib auf der Standardausgabe in $1$ Zeile eine ganze Zahl aus, die den maximalen Wert der Punktzahl der $2$ Spieler darstellt.
Teilaufgaben
- Für $10\%$ der Punkte in den Bewertungsdaten gelten $A \le 10, B \le 10$.
- Für $50\%$ der Punkte in den Bewertungsdaten gelten $A \le 100, B \le 100$.
Beispiel 1
Eingabe
5 4 1 2 3 4 5 3 1 4 1
Ausgabe
2
Dieses Beispiel entspricht dem Beispiel in der Problembeschreibung.
Beispiel 2
Eingabe
6 5 4 1 5 2 3 4 4 5 4 2 3
Ausgabe
3
In diesem Beispiel gibt es $2$ Möglichkeiten, wie die $2$ Spieler eine Punktzahl von $3$ erreichen können.
- Wenn Anna die Karten $1, 2, 3$ abwirft und Bruno die Karten $2, 3$ abwirft, lauten die Stapel der $2$ Spieler von oben nach unten $4, 5, 4$, und die Punktzahl der $2$ Spieler beträgt $3$ Punkte.
- Wenn Anna außerdem die Karten $1, 5, 4$ abwirft und Bruno die obersten Karten $4$ und $5$ abwirft, lauten die Stapel der $2$ Spieler von oben nach unten $4, 2, 3$, und die Punktzahl der $2$ Spieler beträgt $3$ Punkte.