Problemas
효빈이는 호숫가에 있는 2N개의 돌을 보고 이런 생각을 해보았다:
‘하얀 돌과 검은 돌이 각각 N개씩 있으니 하얀 돌과 검은 돌의 위치를 전부 바꾸면 어떨까?’
어차피 할 일이 없던 효빈이는 실제로 돌의 색깔을 뒤바꿔 보려고 한다.
효빈이는 페인트 따위의 도구를 갖고 있지 않기 때문에 돌을 일일이 들어서 옮겨야 한다.
돌을 옮기기에 앞서, 효빈이는 먼저 호수를 따라 한 바퀴 돌면서 자신의 처음 위치(0)에 대한 돌의 위치와 호수의 둘레를 쟀다.
돌들이 매우 무겁기 때문에 돌을 들고 x만큼 이동하려면 x의 힘이 필요하다.
한편 돌을 들고 이동하는 도중에 다른 돌이 있으면 방해가 되기 때문에 돌을 들고 이동하는 구간에는 아무 것도 없어야 한다.
효빈이는 이런 쓸데없는 일에 많은 힘을 투자하기 싫어하기 때문에 최소 힘으로 검은 돌과 하얀 돌의 위치를 바꾸려고 한다.
효빈이에게 필요한 최소 힘을 구하여라.
Entrada
첫 번째 줄에는 호수의 둘레 R과 검은 돌의 개수 N이 주어진다. 1 ≤ N ≤ 100,000, 2N ≤ R ≤ 1,000,000,000 두 번째 줄부터 2N개의 줄에는 돌의 위치 Pk와 돌의 색깔 Ck가 주어진다. Ck가 'B'이면 하얀 돌이고, 'W'이면 검은 돌이다. 검은 돌의 수와 하얀 돌의 수는 같다. 입력예은 Pk가 커지는 순으로 들어온다. 0 ≤ Pk < R
서브태스크 1 : N ≤ 10, R ≤ 50, 검은 돌과 흰 돌이 번갈아 나타남 서브태스크 2 : N ≤ 10, R ≤ 50 서브태스크 3 : N ≤ 100, R ≤ 1,000 서브태스크 4 : N ≤ 5,000, R ≤ 1,000,000 서브태스크 5 : 추가 제약 없음
Salida
만약 효빈이가 검은 돌과 하얀 돌의 위치를 바꿀 수 없다면 '-1' (따옴표 제외)을 출력한다. 그렇지 않으면 효빈이에게 필요한 힘의 최솟값을 출력한다. 답이 매우 클 수 있으므로 유의하여라.
Ejemplo
6 3
0 B
1 W
2 B
3 W
4 B
5 W
6
Debes iniciar sesión para escribir código.