IX Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 11.06.2005

Opis

Mamy N miast położonych po kolei na linii prostej oraz pociąg, który jedzie od pierwszego miasta do ostatniego, zatrzymując się we wszystkich miastach leżących pomiędzy.
Dla każdego miasta i, liczba W[i] oznacza "wielkość" tego miasta. Liczba pasażerów podróżujących z miasta i do miasta j jest równa W[i]*W[j].

Kontrola biletów przeprowadzana jest na odcinku pomiędzy dwoma kolejnymi miastami i obejmuje wszystkich ludzi w pociągu. Na całej trasie przeprowadzanych jest K takich kontroli.
Napisz program, który dla danych parametrów N, K oraz listy wielkości W[1] ... W[N] wyznaczy maksymalną liczbę (różnych) osób, które mogą być skontrolowane.

Wejście

Wejście składa się z pewnej liczby zestawów danych.

W pierwszej linii zestawu danych znajdują się 2 liczby całkowite 2≤N≤2000 oraz 0≤K≤N-1. W drugiej linii znajduje się N liczb całkowitych 1≤W[i]≤5 (dla i=1..N).
Linia kończąca zestawy danych zawiera dwie liczby 0.

Wyjście

Przykładowe wejście

4 1
1 1 1 1
6 2
1 1 1 1 1 1
5 2
1 2 1 1 2
0 0

Przykładowe wyjście

4
12
16