31845번 - 카드 교환

인하대학교 축제가 열리면, 인천 최대 규모의 카지노인 인하 카지노도 함께 문을 연다. 손님들의 더 많은 유입을 원했던 인하 카지노는 모두가 즐길 수 있는 새로운 카드 게임을 만들었다. 새로운 카드 게임의 진행 방식은 다음과 같다.

딜러와 플레이어는 각각 $1$부터 $N$까지의 정수가 적힌 카드를 한 장씩 받는다. 딜러는 아무것도 적혀있지 않은 더미 카드 한 장을 추가로 받는다. 그리고 플레이어는 가진 점수가 $0$인 상태에서 게임을 시작하여 턴을 $M$회 수행한다. 각 턴은 아래와 같은 순서대로 진행된다.

1. 플레이어가 딜러의 패에서 원하는 카드를 하나 가져온다.
2. 플레이어의 패에서 같은 값을 가진 카드 쌍이 만들어진 경우, 그 카드 쌍은 패에서 제거된다. 그리고 해당 카드 쌍에 적힌 값이 $i$라면 플레이어는 $A_i$점을 얻는다. 얻는 점수가 음수일 수 있으며, 플레이어의 점수도 음수가 될 수 있다.
3. 플레이어가 딜러에게 자신의 패에서 원하는 카드를 하나 준다.
4. 딜러의 패에서 같은 값을 가진 카드 쌍이 만들어진 경우 그 카드 쌍은 패에서 제거된다. 이 경우 플레이어는 점수를 얻지 못한다.

$M$번째 턴을 끝내거나 더미 카드를 제외한 모든 카드 쌍이 사라진 순간 게임이 종료된다. 즉, 턴이 수행되는 도중이라도 플레이어가 딜러에게 카드를 줄 수 없다면 게임이 즉시 종료된다.

이 카드 게임에서 게임이 종료되었을 때 플레이어가 얻을 수 있는 최대 점수를 구하는 프로그램을 작성해 보자.

첫 번째 줄에 정수가 적힌 카드의 수 $N$과 게임의 최대 턴 수 $M$이 공백으로 구분되어 주어진다.

두 번째 줄에 각 카드에 대해 플레이어의 패에 카드 쌍이 만들어질 때 얻을 수 있는 점수 $A_1$, $A_2$, $\cdots$, $A_N$이 공백으로 구분되어 주어진다.

플레이어가 얻을 수 있는 최대 점수를 출력한다.

• $1 \le N \le 1{,}000$
• $1 \le M \le 1{,}000$
• $-1{,}000 \le A_i \le 1{,}000$
• $A_i$는 정수이다.

아래에서 설명하는 예시는 예제 입출력의 상황과 다름에 주의한다.

$N = 4$인 경우 플레이어가 첫 턴에서 더미 카드가 아닌, 정수가 적힌 카드를 선택한 턴의 예시는 아래와 같다.

만약 딜러의 패에서 더미 카드를 가져오거나 플레이어가 더미 카드를 딜러에게 준 경우, 아래 예시와 같이 더미 카드를 받은 쪽에서��� 카드 쌍이 만들어지지 않으므로 아무 일도 일어나지 않는다.

아래 예시는 $N = 4$일 때 플레이어가 첫 턴에 더미 카드를 딜러에게 받고 받은 더미 카드를 다시 딜러에게 돌려주는 예시이다.