URI Online Judge | 2548

3D Virtual Museum

By Flávio Zavan, UFPR BR Brazil

Timelimit: 1

Vasya and Petya are visiting the 3D virtual museum of history of the capital. To have fun, they decided to do a little prank. The prank consists on damaging M models among the N exposed ones. Vasya illegally downloads the model’s file, Petya opens it in a 3D editor and replaces historical details by Fibonacci numbers, and then he puts it back into the museum.

Every time a model is damaged, its value is nullified. Since the duo is really evil, they decided to make the museum have the highest loss possible. Given N, M and the value of each exposed models, write a program to calculate the highest loss they can make.


The input contains several test cases. The first line of each test case contains two integers, N (0 ≤ N ≤ 103) and M (0 ≤ MN). The second line contains N integers (between 0 and 1000), the value each model has (in nlogonian dollars), in non-decreasing order.

The input ends with end-of-file (EOF).


For each test case, print a single line containing the highest possible loss they can make.

Input Sample Output Sample

4 2
0 0 2 3
7 1
33 44 55 789 790 791 987