PONDORO - Pondoro

The Pondoro are mysterious creatures with massive mouths.

They live in a mysterious world of length n, where the weather of this world is divided into blocks on a line, where some spots are raining and some spots are dry.

You can think of their world as a string which contains the characters R and ., where R means that spot is raining and . means the spot is dry. For example the string R..RR..RRR represents the world with 6 spots that are raining and four spots that are dry.

You are given m Pondoro. Each of different length mouths.

A Pondoro with a mouth of length L can take the water from L continuous blocks of the line (if a block has rain on it then it will supply one litre of water per second).

The best Pondoro will consume a lot of water, but also be small so that it doesn't use a lot of energy.

Given the lengths of the Pondoro mouths (all unique lengths) determine Pondoro which (depending on where it stands) can consume the maximum amount of water out of all the Pondoros, but is also as small as possible (in terms of mouth length).

Input

Your first line will contain two space-separated integers n (n <= 100,000) and m (m <= 100,000).

Your next line will contain a string of length n, which contains only the characters R and ., where R means that spot is raining and . means the spot is dry.

Your next line will contain m space-separated integers representing the lengths of the mouths of the Pondoros.

Output

A single integer representing the length of the mouth of the best Pondoro out of all the Pondoros given.

Input 1
12 3
R..RR.RR..RR
4 5 6

Output 1
5
Explanation 1

Notice that although a length 6 mouth can consume 4 litres of water per second when standing at position 4 (1-indexed), so can a length 5 mouth, and length 5 is smaller and therefore better.

Input 2
12 2
R..RR.RR..RR
7 8

Output 2
8
Input 3
11 2
R.RR.RR..RR
7 8

Output 3
7

Added by:jslew
Date:2022-09-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NCSHARP JULIA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.