심포니
시간 제한1초메모리 제한512 MB
배열 A의 모든 원소에 정수 X를 더한 뒤 최대 K개의 원소를 임의의 값으로 바꿔 B와의 절댓값 차이 합을 최소로 만든다.
문제
작곡가 마린의 빼어난 재능을 믿는 사람은 거의 없었다. 그가 9번째 교향곡을 작곡한 날까지는 특히 그랬다.
교향곡은 정수인 주파수들의 나열로 나타낼 수 있다. 마린은 자신의 재능을 증명하고 이 교향곡이 흔한 곡 중 하나가 아님을 보이기 위해, 역사상 최고의 음악가 스체판의 고대 교향곡 "작은 밤의 축제"와 비교하기로 했다. 별들은 이 두 교향곡의 길이가 N으로 같다고 말하고 있다.
마린은 두 교향곡을 종이 위에 위아래로 나란히 적어 비교한다. 교향곡의 다양성은 대응하는 주파수 차의 절댓값의 합으로 정의된다. 길이 N인 교향곡 A와 B의 다양성은 다음과 같다.
[\sum_{i=1}^{N}{\left| A_i - B_i \right|}]
두 교향곡을 비교하기 전에 마린은 두 가지를 한다. 먼저 각 주파수에 정수 X를 더해 자신의 교향곡을 조율한다. 그다음 꿈에서 영감을 받았고 뛰어난 작곡가라면 누구나 그러듯이, 최대 K개의 주파수를 다른 임의의 주파수 값으로 바꾼다.
마린은 자신의 교향곡이 스체판의 교향곡과 최대한 비슷해지도록, 즉 정의된 다양성이 최소가 되도록 X를 정하고 K개의 주파수를 바꿀 것이다. 마린을 도와 스체판의 교향곡과의 최소 가능한 다양성을 계산하라.
입력
첫째 줄에 정수 N과 K가 주어진다 (1 ≤ N ≤ 100 000, 0 ≤ K ≤ N). 이는 문제 본문에 나온 수들이다.
둘째 줄에 마린의 교향곡 주파수를 나타내는 N개의 정수 Ai가 주어진다 (-1 000 000 ≤ Ai ≤ 1 000 000).
셋째 줄에 스체판의 교향곡 주파수를 나타내는 N개의 정수 Bi가 주어진다 (-1 000 000 ≤ Bi ≤ 1 000 000).
출력
한 줄에 마린과 스체판의 교향곡 사이의 최소 가능한 다양성을 출력한다.