시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 256 MB 2 0 (0%) 0
문제
도시 팔렘방은 무시강에 의해 두 구역으로 나눠진다. 그들을 구역 $A$, 구역 $B$라고 부르자. 각 구역에는 강가를 따라 정확하게 $1\,000\,000\,001$채의 빌딩이 있고 편의상 그들의 $0$번부터 $1\,000\,000\,000$번으로 번호를 붙였다. 모든 인접한 빌딩들간의 거리는 단위 거리로 $1$이다. 강의 너비 역시 단위 거리로 $1$이다. 구역 $A$의 $i$번 빌딩은 구역 $B$의 $i$번 빌딩과 정확하게 마주보는 위치에 있다. $N$명의 시민들이 이 도시에서 일을 하며 살고 있다. $i$번 시민의 집은 구역 $P_i$의 $S_i$번 빌딩에 있으며 그의 사무실은 구역 $Q_i$의 $T_i$번 빌딩에 있다. 만약 누군가가 그의 집에서 사무실로 갈때 강을 건너야 한다면 그는 보트를 타고 건너야 한다. 이것이 그동안 불편한 점이었기 때문에 정부는 강을 건너는 최대 $K$개의 다리를 건설하기로 결정하여 시민들이 차를 통해 통근을 할 수 있도록 하고자 한다. 각 다리들은 정확하게 두 구역의 마주보는 빌딩 사이에 건설되어야 한다. 그리고 다리들은 강과 수직하게 지어져야 한다. 또한 다리끼리 서로 겹치면 안된다. 정부가 최대 $K$개의 다리를 지은 후 $i$번 시민이 그의 집에서 사무실까지 운전을 해서 가는데 드는 최소 거리를 $D_i$라고 하자. 합 $D_1 + D_2 + ... + D_N$을 최소화하도록 다리를 건설하는 방법을 구하라.
입력
첫째 줄에 띄어쓰기로 구분된 두 개의 정수 $K, N$이 주어진다. 다음 $N$개의 줄에는 4개의 값 $P_i, S_i, Q_i, T_i$가 주어진다.
출력
한 줄에 거리들의 합의 최소값을 출력한다.
힌트
#### 예제 입력 1 ``` 1 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 ``` #### 예제 출력 1 ``` 24 ``` #### 예제 입력 2 ``` 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 ``` #### 예제 출력 2 ``` 22 ``` #### 설명 두 입력 예제에 대한 그림은 아래와 같다. 예제 1에 대한 가능한 해법 중 하나는 아래와 같다. 분홍색 선이 다리를 의미한다. 그리고 아래는 예제 2에서 가능한 해법이다. #### 서브태스크 모든 서브태스크에 대해 - $P_i$와 $Q_i$는 문자 'A' 혹은 'B'이다. - $0 ≤ S_i, T_i ≤ 1,000,000,000$ - 한 빌딩에 $1$개 이상의 집 혹은 사무실(혹은 둘 다)이 존재할 수 있다. - 서브태스크 1 (8점) : $K = 1, 1 ≤ N ≤ 1,000$ - 서브태스크 2 (14점) : $K = 1, 1 ≤ N ≤ 100,000$ - 서브태스크 3 (9점) : $K = 2, 1 ≤ N ≤ 100$ - 서브태스크 4 (32점) : $K = 2, 1 ≤ N ≤ 1,000$ - 서브태스크 5 (37점) : $K = 2, 1 ≤ N ≤ 100,000$