11906번 - 돌 옮기기

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

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

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

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

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

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

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

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