돌 옮기기 Batch Compilation commands

민혁이는 호숫가에 있는 $2N$개의 돌을보고 문뜩 이런 생각을 합니다. ‘하얀 돌과 검은 돌이 각각 N개씩 있으니 하얀 돌과 검은 돌의 위치를 서로 바꾸면 어떨까?’

어차피 할 일이 없던 민혁이는 실제로 돌의 색깔을 뒤바꿔 보려고 합니다. 민혁이는 페인트 따위의 도구를 갖고 있지 않기 때문에 돌을 일일이 들어서 옮겨야 합니다.

돌을 옮기기에 앞서, 민혁이는 먼저 호수를 따라 한 바퀴 돌면서 민혁이의 처음 위치(0)에 대한 돌의 위치와 호수의 둘레를 쟀습니다.

돌들이 매우 무겁기 때문에 돌을 들고 $x$만큼 이동하려면 $x$의 힘이 필요합니다. 한편, 돌을 들고 이동하는 도중에 다른 돌이 있으면 방해가 되기 때문에 돌을 들고 이동하는 구간에는 다른 돌이 있으면 안 됩니다.

민혁이는 이런 쓸데없는 일에 힘을 투자하기 싫어하기 때문에 최소 힘으로 검은 돌과 하얀 돌의 위치를 바꾸려고 합니다. 민혁이에게 필요한 최소 힘을 구하세요.

입력 형식

첫 번째 줄에는 호수의 둘레 $R$과 검은 돌의 개수 $N$이 주어집니다. 두 번째 줄부터 $2N$개의 줄에는 돌의 위치 $P_{k}$와 돌의 색깔 $C_{k}$가 주어집니다. $C_{k}$가 'B' (따옴표 제외)이면 하얀 돌이고, 'W' (따옴표 제외)이면 검은 돌입니다. 검은 돌의 수와 하얀 돌의 수는 같고, 입력은 $P_{k}$가 커지는 순으로 주어집니다.

출력 형식

만약 민혁이가 검은 돌과 하얀 돌의 위치를 바꿀 수 없다면 '-1' (따옴표 제외)을 출력합니다. 그렇지 않으면 민혁이에게 필요한 힘의 최솟값을 출력합니다. 답이 매우 클 수 있으므로 유의하세요.

참고

돌의 크기는 0이라고 가정해도 좋으며, 민혁이가 돌을 들었다 놓는 위치가 정수일 필요는 없습니다. 하지만 돌을 모두 옮긴 후에는 옮기기 전의 상태에서 색만 바뀐 상태가 되어야 합니다.

서브태스크

이 문제의 채점 방식은 다른 문제와 많이 다릅니다. 채점 시간을 빠르게 하기 위해, $i$번 서브태스크에서 틀린 답안이 하나라도 존재한다면 그 뒤의 서브태스크는 0점 처리합니다.

만약 여러분의 프로그램이 1, 2번 서브태스크의 모든 데이터에 대해 올바른 정답을 출력하고, 서브태스크 3에서 틀린다면, 서브태스크 4,5는 채점하지 않고 바로 0점 처리되어 이 제출에 대한 여러분의 점수는 17점이 됩니다.

모든 서브태스크에 대해

• $ 0 \le P_{k} \le R$

서브태스크 1 (6점)

• $ 1 \le N \le 10$
• $ 2N \le R \le 50$
• 검은 돌과 흰 돌이 번갈아 나타납니다. 즉, 모든 $1 \le k < 2N$에 대해서 $C_k \neq C_{k+1}$입니다.

서브태스크 2 (11점)

• $ 1 \le N \le 10$
• $ 2N \le R \le 50$

서브태스크 3 (16점)

• $ 1 \le N \le 100$
• $ 2N \le R \le 1,000$

서브태스크 4 (23점)

• $ 1 \le N \le 5,000$
• $ 2N \le R \le 1,000,000$

서브태스크 5 (44점)

• $ 1 \le N \le 200,000$
• $ 2N \le R \le 1,000,000,000$

입력과 출력의 예

예제 1

입력

6 3
0 B
1 W
2 B
3 W
4 B
5 W

출력

6

예제 2

입력

10 3
0 B
1 W
3 B
4 W
7 W
9 B

출력

-1