0 이상 500 이하의 숫자들로 이루어진 수열이 있다.

이 수열들을 주어지는 구간 수로 적절히 나누어서 구간 값의 합을 최대로 하고 싶다. 이 문제에서는 구간이란 연속된 둘 이상의 숫자를 묶는 것이다. 다음 그림은 10 개의 숫자로 이루어진 수열에서 구간으로 나눈 예이다.

구간 값이란 어떤 구간에서의 최대값과 최소값을 뺀 것이다.

예를들어 , 네 번째 구간의 구간 값은 9 - 3 = 6 이다.위의 방법으로 구간을 나누었을 때 구간 값의 합은 3 + 6 + 5 + 6 = 20 이다. 위의 수열에서는 이렇게 나누는 방법으로 최대 구간값의 합을 얻을 수 있다.

수열이 주어질 때, 이 수열을 주어지는 구간으로 적절히 나눠 구간 값의 합을 최대로 하는 프로그램을 작성하시오.

입력 형식

• 첫 줄에는 수열의 길이 N( 2 <= N <=100)이 주어지고,
• 다음 줄에는 구간 수 M ( 1 <= M <= N/2 )
• 다음 줄에는 수열을 이루는 N 개의 숫자(0 이상 500 이하)가 빈칸을 두고 주어진다.

출력형식

• 구한 구간 값의 합을 출력한다.

입출력 예

입력

10
4
2 5 7 1 3 4 8 6 9 3

출력

20