Problembeskrivelse
Det finnes mange kort, hvert med et heltall fra $1$ til $1000$ skrevet på seg. Anna og Bruno spiller følgende spill med disse kortene.
Anna har en bunke som består av $A$ kort, og Bruno har en bunke som består av $B$ kort. Anna kaster et valgfritt antall kort ($0$ kort er også tillatt) fra sine $A$ kort for å lage en ny bunke. Bruno kaster noen kort ($0$ kort er også tillatt) fra toppen og noen kort ($0$ kort er også tillatt) fra bunnen av bunken sin med $B$ kort for å lage en ny bunke. De gjenværende kortene endrer imidlertid ikke rekkefølge når kort kastes. Hvis de $2$ bunkene som lages på denne måten er like, blir antallet kort i en av bunkene poengsummen til de $2$ spillerne. Her er $2$ bunker like hvis antallet kort $n$ i hver bunke er det samme, og for hvert $i$-te kort ovenfra ($1 \le i \le n$) er heltallene skrevet på kortene helt like.
Anta for eksempel at Anna har en bunke med $5$ kort med heltallene $1, 2, 3, 4, 5$ skrevet i rekkefølge ovenfra, og at Bruno har en bunke med $4$ kort med heltallene $3, 1, 4, 1$ skrevet i rekkefølge ovenfra. Hvis Anna nå kaster kortene $2, 3, 5$, og Bruno kaster det øverste kortet $3$ og det nederste kortet $1$, blir bunkene til de $2$ spillerne like. Siden antallet kort i en av de gjenværende bunkene er $2$, får de $2$ spillerne poengsummen $2$.
Vi ønsker å finne den maksimale verdien av poengsummen til de $2$ spillerne.
Oppgave
Gitt informasjon om kortbunkene som Anna og Bruno har, skriv et program for å finne den maksimale verdien av poengsummen til de $2$ spillerne.
Begrensninger
- $1 \le A \le 5000$: Antallet kort i Annas bunke.
- $1 \le B \le 5000$: Antallet kort i Brunos bunke.
- Heltallene som er skrevet på kortene er mellom $1$ og $1000$, inkludert.
Inndata
Les følgende data fra standard inndata.
- På den $1$. linjen står heltallene $A, B$, adskilt med et mellomrom.
- På den $2$. linjen står $A$ heltall adskilt med mellomrom; det $i$-te heltallet ($1 \le i \le A$) representerer heltallet skrevet på det $i$-te kortet ovenfra i Annas bunke.
- På den $3$. linjen står $B$ heltall adskilt med mellomrom; det $j$-te heltallet ($1 \le j \le B$) representerer heltallet skrevet på det $j$-te kortet ovenfra i Brunos bunke.
Utdata
Skriv ut på standard utdata på $1$ linje et heltall som representerer den maksimale verdien av poengsummen til de $2$ spillerne.
Deloppgaver
- For $10\%$ av poengene i testdataene er $A \le 10, B \le 10$ oppfylt.
- For $50\%$ av poengene i testdataene er $A \le 100, B \le 100$ oppfylt.
Eksempel 1
Inndata
5 4 1 2 3 4 5 3 1 4 1
Utdata
2
Dette eksempelet tilsvarer eksempelet i problembeskrivelsen.
Eksempel 2
Inndata
6 5 4 1 5 2 3 4 4 5 4 2 3
Utdata
3
I dette eksempelet er det $2$ måter for de $2$ spillerne å få poengsummen $3$ på.
- Når Anna kaster kortene $1, 2, 3$ og Bruno kaster kortene $2, 3$, blir bunkene til de $2$ spillerne $4, 5, 4$ i rekkefølge ovenfra, og poengsummen til de $2$ spillerne blir $3$ poeng.
- Også når Anna kaster kortene $1, 5, 4$ og Bruno kaster de øverste kortene $4$ og $5$, blir bunkene til de $2$ spillerne $4, 2, 3$ i rekkefølge ovenfra, og poengsummen til de $2$ spillerne blir $3$ poeng.