ITPSEQ - Another Problems of Sequence

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)

Added by:Gầy :))
Date:2014-09-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Đỗ Đức Đông

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.