B. Painel circular

Time limit: 3000 msMemory limit: 256 MB

Um painel tem $n$ lâmpadas em um círculo, numeradas de $1$ a $n$ , inicialmente apagadas. Há um botão para cada posição. Apertar o botão $i$ custa $c_i$ e inverte o estado das $k$ lâmpadas consecutivas que começam em $i$ , seguindo a ordem circular. Depois da posição $n$ vem a posição $1$ .

Você pode apertar cada botão quantas vezes quiser. Determine o menor custo total para obter exatamente o estado indicado pela cadeia $s$ , em que 1 significa acesa e 0 significa apagada. Se isso for impossível, informe esse fato.

Input

A primeira linha contém $n$ e $k$ ( $1 \le k \le n \le 200000$ ). A segunda contém uma cadeia $s$ de comprimento , formada por e . A terceira contém inteiros ().

Output

Imprima o menor custo total, ou -1 se não existir uma sequência de apertos válida.

Samples

Sample 1

Input

4 2
1100
5 2 3 4

Output

Basta apertar o botão $1$ . A outra escolha sem repetições que produz esse estado custa $9$ .

Sample 2

Input

4 2
1000
1 1 1 1

Output

-1

Cada aperto inverte duas lâmpadas; não é possível terminar com exatamente uma acesa.