Limits 3s, 512 MB

You are given a binary string SS and kk distinct indices to perform an operation.

The operation is like below:

You can shuffle the given indices any number of times (possibly zero).

You have to find out the maximum length of a palindromic subsequence of string SS after shuffling.

Example of an operation: Say SS = “001110”, Let the indices be [1,3,5][1, 3, 5]. Then after the operation the string content can be, 100110.

Input

The first line of input contains a string SS and an integer kk

The next line will contain kk space separated integers a1,a2,,aka_1, a_2, \ldots, a_k denoting the indices that you can shuffle, all of them are guaranteed to be distinct.

Constraints

1S5001\le|S|\le500

0kS0 \le k \le |S|

1aiS1\le a_i\le |S|

Output

Output one line containing the output, the maximum length of any palindromic subsequence after the operation.

Sample

InputOutput
10010 2
1 2
5

Submit

Login to submit.

Statistics

64% Solution Ratio
Asif17rEarliest, 8M ago
yeehawFastest, 0.2s
Asif17rLightest, 5.5 MB
yeehawShortest, 1743B
Toph uses cookies. By continuing you agree to our Cookie Policy.