보물 상자 열기

어피치는 전설 속의 보물을 찾기 위해 여행을 떠났고, 여러 관문을 돌파한 끝에 보물이 들어 있으리라 추정되는 상자를 찾았다. 하지만 상자에는 잠금장치가 걸려 있었고, 그 아래에는 "상자를 열려면 상자 아래의 글자들을 잘 바꾸어 앞으로 읽으나 뒤로 읽으나 똑같아지도록 하라"라는 글귀가 쓰여 있었다.

상자 근처를 살펴보니 상자 아래에 알파벳이 쓰인 석판 여러 장이 일렬로 놓여 있었다. 상자 주위에는 알파벳이 쓰인 석판이 훨씬 더 많았다. 석판들을 적절히 교체하여 상자 아래 일렬로 놓인 석판들을 회문(앞에서 뒤로 읽으나 뒤에서 앞으로 읽으나 똑같은 낱말, 숫자, 또는 문장)으로 만들면 상자가 열리는 듯하다. 어피치는 체력이 얼마 남지 않아서, 체력을 최대한 아껴 보물을 얻고자 한다. 석판을 교체하는 데 드는 체력은 석판마다 다르다. 또한 한 칸 이동할 때마다 체력이 $c$만큼 소모된다. 예를 들어 이전 위치가 $i$번째 석판이었는데 이번에 $j$번째 석판을 교체하고자 한다면, 그 위치까지 이동하는 동안 $c \cdot |j - i|$의 체력이 소모된다. $N$개의 석판 각각에 대해, 그 석판이 있는 위치에서 시작할 때 보물을 얻기 위해 소모되는 최소 체력을 구하시오.

첫 줄에 테스트 케이스의 개수 $T$($1 \le T \le 100,000$)가 주어진다.

다음 줄부터 $T$개의 테스트 케이스가 아래 형식으로 주어진다.

첫째 줄에 석판의 개수 $N$($1 \le N \le 1,000,000$)과 한 칸 이동할 때 소모되는 체력 $c$($1 \le c \le 10^9$)가 주어진다.

둘째 줄에 길이 $N$인 문자열이 주어진다. 문자열의 $i$번째 문자는 $i$번째 석판에 쓰인 문자이며, 각 문자는 알파벳 대문자이다.

셋째 줄에 $N$개의 정수가 주어진다. $i$번째 수는 $i$번째 석판을 교체하는 데 소모되는 체력이며, 1 이상 $10^9$ 이하이다.

주어지는 모든 $N$의 합은 1,000,000을 넘지 않는다.

각 테스트 케이스에 대해, 각 석판이 있는 위치에서 시작했을 때 어피치가 소모해야 하는 최소 체력을 공백으로 구분하여 한 줄에 출력한다.