Statement
양의 정수로 이루어진 길이 의 수열 가 주어진다.
수열의 불균형도를 수열의 원소의 최댓값과 최솟값의 차로 정의한다.
세종이는 다음 연산을 한 번 이상 수행해야 한다.
- 수열 에서 개 이상 개 이하의 원소를 선택한다.
- 선택하지 않은 원소들의 합을 라고 할 때, 선택한 각 원소에 를 더한다.
세종이가 만들 수 있는 수열의 불균형도의 최솟값을 구하여라.
Input
첫 번째 줄에 두 정수 과 가 공백으로 구분되어 주어진다.
두 번째 줄에 개의 정수 이 공백으로 구분되어 주어진다.
Output
첫 번째 줄에 만들 수 있는 수열의 불균형도의 최솟값을 출력한다.
Samples
Sample 1
Input
3 1
1 2 2
Output
3
Sample 2
Input
3 1
2 2 2
Output
4
Sample 3
Input
6 3
2 5 7 8 9 11
Output
23