Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
101 - ZOJ Monthly, December 2010 - B
Doraemon's Number Game

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Doraemon and Nobita are playing a number game. First, Doraemon will give Nobita N positive numbers. Then Nobita can deal with these numbers for two rounds. Every time Nobita can delete i (2 ≤ iK) numbers from the number set. Assume that the numbers deleted is a[ 1 ], a[ 2 ] ... a[ i ]. There should be a new number X = ( a[ 1 ] * a[ 2 ] * ... * a[ i ] + 1 ) to be inserted back into the number set. The operation will be applied to the number set over and over until there remains only one number in the set. The number is the result of round. Assume two results A and B are produced after two rounds. Nobita can get |A - B| scores.

Now Nobita wants to get the highest score. Please help him.

Input

Input will contain no more than 10 cases. The first line of each case contains two positive integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 50). The following line contains N positive integers no larger than 50, indicating the numbers given by Doraemon.

Output

For each case, you should output highest score in one line.

Sample Input

6 3
1 3 4 10 7 15

Sample Output

5563

Hint

For most cases, N ≤ 20


Author: XU, Shicheng
Contest: ZOJ Monthly, December 2010
Submit    Status