Min Time After Which the Password Becomes Irrecoverable

The initial lowercase password has length n. At second t, position attackOrder[t] (1-based) is changed to *, and attackOrder is a permutation of 1..n. A damaged substring is a non-empty contiguous substring containing at least one *, counted separately by start and end positions. Find the second at which their number first reaches or exceeds m. When m=0, output 1, as specially required by the source. The source's main text mistakenly wrote the threshold as n; it is corrected according to the parameter m and both examples.

输入格式

The first line contains n m, the second line the password, and the third line n values attackOrder. 1≤n≤800000, 0≤m≤n(n+1)/2, the password is lowercase, and attackOrder is a permutation of 1..n.

输出格式

Output a single integer, the answer.

样例 1

输入：

5 10
bcced
2 3 1 4 5

输出：

2

样例 2

输入：

4 10
abcd
4 1 3 2

输出：

4

样例 3

输入：

1 0
a
1

输出：

1

样例说明

The answers are 2, 4 and 1. In the first example there are 8 damaged substrings at second 1 and 11 at second 2, which is the first time the count reaches 10.