31589번 - 포도주 시음

문제

산들이는 포도주(와인)를 좋아한다. 그는 마트에서 팔고 있는 $N$종류의 포도주를 사서 음미하려고 한다. 포도주를 한 병 단위로 사기엔 산들이가 금전적으로 부담이 있기 때문에 그는 작은 용기에 담긴 포도주를 살 것이다. 마트에서 팔고 있는 $N$종류의 포도주들은 각각 $T_1,ドル $T_2,ドル …, $T_N$의 맛을 갖고 있다. 맛의 값이 높은 포도주가 더 맛있는 포도주이다.

산들이가 맛있는 포도주를 마시다가 맛없는 포도주를 마시면 그 맛이 감기약 맛을 방불케 하기 때문에 사실상 0의 맛을 느낀다. 하지만 맛없는 포도주를 마시다가 맛있는 포도주를 마시면 그 두 포도주의 맛 차이만큼 맛을 느낀다. 예외적으로 가장 먼저 마시는 포도주의 맛은 그 포도주 본연의 맛 그대로이다.

산들이는 주량이 매우 적기 때문에 $K$종류의 포도주를 먹으면 취하여 잠자리에서 뻗어버린다. 따라서 산들이는 $N$종류의 포도주들 중에서 $K$종류를 골라 마실 것이다. 산들이는 $K$종류의 포도주를 마시면서 느낄 수 있는 맛의 합을 극대화하려고 한다.

산들이를 도와 포도주를 얼마나 맛있게 음미할 수 있는지 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 포도주의 수 $N$과 산들이의 주량 $K$가 주어진다. (1ドル \le K \le N \le 300,000円$)

두 번째 줄에는 $N$개의 포도주의 맛 $T_i$가 주어진다. (1ドル \le T_i \le 1,000円,000円,000円$)

출력

첫 번째 줄에 산들이가 느끼는 맛의 합의 최댓값을 출력한다.

제한

힌트