Card Exchange

Time limit1sMemory limit1024 MB

Summary

Given N card values with point values A_i and M turns of trading cards with a dealer, find the maximum score the player can end with.

Level: Medium6 of 10
Topics: Greedy, Dynamic programming, Sorting
Solved: No attempts yet

Problem

When the Inha University festival opens, Inha Casino, the largest casino in Incheon, opens too. Hoping to draw more guests, Inha Casino created a new card game that everyone can enjoy. The game works as follows.

The dealer and the player each receive one card for every integer from $1$ to $N$ , with that integer written on it. The dealer also receives one blank dummy card. The player starts with a score of $0$ and takes $M$ turns. Each turn proceeds in this order.

The player takes any one card they want from the dealer's hand.
If the player's hand now contains a pair of cards with the same value, the pair is removed from the hand. If the value on the pair is $i$ , the player gains $A_i$ points. The gained points can be negative, and the player's score can also become negative.
The player gives the dealer any one card they want from their hand.
If the dealer's hand now contains a pair of cards with the same value, the pair is removed from the hand. In this case the player gains no points.

The game ends right after the $M$ -th turn, or as soon as every pair except the dummy card is gone. If the player cannot give a card to the dealer during a turn, the game ends immediately.

Write a program that finds the maximum score the player can have when the game ends.

Input

The first line contains the number of cards $N$ and the maximum number of turns $M$ , separated by a space.

The second line contains the points $A_1, A_2, \cdots, A_N$ that the player gains when a pair with that value is formed, separated by spaces.

Output

Print the maximum score the player can earn.

Constraints

$1 \le N \le 1{,}000$
$1 \le M \le 1{,}000$
$-1{,}000 \le A_i \le 1{,}000$
$A_i$ is an integer.

Hint

The example below differs from the situation in the sample input and output, so take care with it.

With $N = 4$ , the player picks a card with a number written on it, not the dummy card, on the first turn.

If the player takes the dummy card from the dealer's hand, or gives the dummy card to the dealer, no pair forms on the receiving side, so nothing happens.

The example below shows $N = 4$ . On the first turn, the player receives the dummy card from the dealer and then gives that same dummy card back.

Examples2

Example 1
Input
```
8 10
3 1 -6 -4 -5 9 -10 -1
```
Expected output
```
13
```
Example 2
Input
```
5 3
3 1 2 4 1
```
Expected output
```
9
```