문제
정올시는 좌표 0 이상 L 이하 범위의 길로 이루어진 도시이다. 정올시의 모든 정수 좌표 지점에는 버스 정류장이 설치되어 있다. 정올시에는 N명의 사람들이 살고 있는데, 각 사람들은 좌표 X_i에서 살고 있다.
우리는 정올시의 한 곳에 철도역을 세울 것이다. 철도역은 정수 좌표에 세워야 하며, N명의 사람들이 철도역으로 가면서 내는 버스 요금의 합이 최소가 돼야 한다. 버스 요금은 이동거리에 따라 달라지는데, 버스를 타고 i만큼 이동했으면 C_i원을 지불해야 한다. 사람이 사는 곳에 철도역이 있다면, 돈을 내지 않는다.
사람들의 정보가 주어지면 철도역을 적절한 지역에 설치하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 정올시의 크기 L과 사람의 수 N이 주어진다. (1 ≤ L, N ≤ 100,000)
두 번째 줄에는 버스를 타고 1, 2, …, L만큼 이동하는 비용 C_i가 주어진다. (1 ≤ C_1 < C_2 < … < C_L ≤ 1,000,000,000, C_1 ≤ C_i - C_i-1 ≤ C_i+1 - C_i)
세 번째 줄에는 각 사람이 사는 위치 X_i가 주어진다. (0 ≤ X_i ≤ L)
전체 데이터의 25%는 C_i = i이다.
출력
철도역을 적절히 세웠을 때, 사람들이 내는 버스 요금의 합을 출력한다.
예제
10 5
1 2 3 4 5 6 7 8 9 10
2 4 5 8 10
12
태그
로그인해야 코드를 작성할 수 있어요.