5th Job Advancement

Kipa, a MapleStory newbie, has finally reached level 200 and wants to make their character stronger using a system called 5th Job Advancement. To advance to the 5th job, they must first obtain an item called an Arcane Stone through a quest. Activating an Arcane Stone lets the character collect the experience they earn into the stone. To advance to the 5th job, the character must complete n quests in total and receive n Arcane Stones, and collecting at least 500 million experience in each Arcane Stone grants the qualification to advance to the 5th job.

Completing the i-th quest grants a_i experience and the i-th Arcane Stone. Since the experience from quests is the same kind of experience as the experience from hunting, the Arcane Stones that are active when the reward experience of the i-th quest is received each gain a_i experience.

These are the Arcane Stones in Maple World. Nice, aren't they?

In the original MapleStory, only one Arcane Stone can be active at a time, and each Arcane Stone can hold at most 500 million experience. However, Kipa, a Maple newbie who was confident in hacking, hacked the server, removed the maximum experience limit of the Arcane Stones, and changed it so that up to k Arcane Stones can be active at the same time. Therefore, the reward experience of one quest can be added to multiple Arcane Stones. For example, if the 1st and 3rd Arcane Stones are active and the 2nd quest is completed, granting 100,000 experience and the 2nd Arcane Stone, then 100,000 experience is added to each of the 1st and 3rd Arcane Stones, and the 2nd Arcane Stone is received with 0 collected experience.

Kipa can complete the quests in any order, but cannot complete the same quest more than once. While completing quests, Kipa wants to activate or deactivate Arcane Stones appropriately to maximize the total experience collected in the Arcane Stones. After all, a larger total collected experience feels good no matter what. Please find this value for Kipa!

The first line contains the integers n and k (1 ≤ k ≤ n ≤ 3 · 10^5).

The second line contains n integers separated by spaces. The i-th integer is a_i, which is greater than 0 and less than or equal to 10^8.

Print the maximum total experience Kipa can collect in the Arcane Stones on the first line.

First complete the 1st quest and activate the 1st Arcane Stone after receiving it. Then complete the 3rd quest and activate the 3rd Arcane Stone after receiving it. Finally, complete the 2nd quest.

In this case, 500 experience is collected in the 1st Arcane Stone and 300 in the 3rd, for a total of 800, and the total collected experience cannot be made larger than this.