Little Stars
Twinkle, twinkle, little star,
How I wonder what you are!
Up above the world so high,
Like a diamond in the sky.
When the blazing sun is gone,
When he nothing shines upon,
Then you show your little light,
Twinkle, twinkle, all the night.
The end your nature does foretell
No more humans it does spell
When stars align and planets curve
All we may do is observe
You have been watching the night sky for many years, and have a log of the major event that occurred every day. For example:
- 14/08, I saw two shooting stars
- 15/08, Venus was visible to the naked eye
- 16/08, There was a full moon tonight
You now have a vast collection of records, and have recently been told of a great cataclysm that will certainly occur when a certain combination of events happen, one day after the other:
- On the first day, three shooting stars will be visible in the night sky
- For the next 3 days, three planets will be visible to the naked eye
- On the next day, the brightest star in the sky will be temporarily occluded by the moon
- Then, the world will end.
All prophesized events will only occur once, or in a contiguous group of days. For example, it is impossible to prophesise a single shooting star, then 3 days of planets being visible, then another single shooting star day.
You'd like to know at any point in your log, the furthest along this sequence of these events we have ever ventured, with no gaps.
Because you see these events so often, you've categorised them into easy to write but hard to remember hexadecimal strings.
So, your log for the week might be:
A4B FF3 B21 CD9 8D0 05C ABD
And the prophesized events might be:
CD9 8D0 A4B FF3 B21 33C 000
The longest sequence of events that actually occurred this week is CD9 8D0
. It is not A4B FF3 CD9
- we need to start at the beginning of the sequence of cataclysm events.
Input
Input will contain 2 space separated integers, and . These are the lengths of your log, and the log of cataclysm events
2 lines will follow, each containing space-separated strings representing events. The first line will contain strings, representing your log, and the second will take strings, representing the cataclysm events
Output
Output a single integer, representing the furthest along the cataclysm events you've ever recorded.
Constraints
- Each string will contain at most characters
Example 1
For input
7 7
A4B FF3 B21 CD9 8D0 05C ABD
CD9 8D0 A4B FF3 B21 33C 000
The correct output is
2
Since the furthers we get along the cataclysm is CD9 8D0
.
Example 2
For input
11 6
A B C A A B B C C C D
A B B C C D
The correct output is
5
Since the furthers we get along the cataclysm is A B B C C
.
Comments