문제
마얌은 전기 공학자 이다. 그녀는 통신 타워에서 전선 연결을 설계하고 있다.
타워에는 서로 다른 높이들에 위치하는 연결점들이 존재한다.
전선은 임의의 두 연결점을 연결하는데 사용될 수 있다.
각 연결점은 임의개수의 전선들에 연결될 수 있다.
두 가지 종류의 연결점들이 존재하는데 빨간점과 파란점이다.
문제에서 타워는 직선으로, 연결점들은 직선 위 음이 아닌 정수 좌표에 놓인 빨간점과 파란점으로 생각한다.
전선의 길이는 그것이 연결하는 두 연결점들 사이의 거리이다.
당신은 마얌이 다음을 만족하는 전선 연결 방식을 찾도록 도와야 한다:
1. 각 연결점은 자신과 다른 색깔의 연결점과 적어도 하나의 전선으로 연결되어야 한다.
2. 전선들의 총 길이가 최소화 되어야 한다.
빨간점과 파란점의 좌표가 주어지면 전선들의 총 길이의 최솟값을 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 숫자, 알파벳으로 이루어진 길이 100 이하의 문자열이 주어진다. 해당 값은 의미없는 값이다.
두 번째 줄에는 N, M이 주어진다. (1 ≤ N, M ≤ 100,000)
세 번째 줄에는 빨간점의 좌표가 증가하는 순서대로 주어진다.
네 번째 줄에는 파란점의 좌표가 증가하는 순서대로 주어진다.
모든 점의 좌표는 0 이상 1,000,000,000 이하의 정수이며 서로 다르다.
출력
첫 번째 줄에 전선을 연결하는 최소 비용을 출력한다.
예제1
입력
JUNGOL
45
1237
045910
출력
10
출처
IOI 2017 day1 2