By Flávio Zavan, UFPR Brazil
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 ≤ M ≤ N). 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|