For a sequence of integer A with n element and interger k. Find squence of index 1<=i_1<i_2<...<i_3k<=n be content with:

S = (a_i1 - a_i2 + a_i3) + (a_i4 - a_i5 + a_i6) + ... + (a_i(3k-2) - a_i(3k-1) + a_i(3k)) maximum.

Input

- First line are tow interger n and k (0<3k<=n).

- Second line have n interger a1, a2, ..., an (|ai| <=10^9)

Output

- The value maximum of S.

Example

Input:
5 1
1 2 3 4 5
Output:
4

Limit:

Subtask 1: n<=400; k=1 (15 test)

Subtask 2: n<=4000; k=1 (15 test)

Subtask 3: n<=40000; k=1 (15 test)

Subtask 4: n<=4000; k=2 (15 test)

Subtask 5: n<=400; k<=10 (20 test)

Subtask 6: n*k<=40000 (20 test)