카드 교환

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

딜러와 플레이어는 각각 $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$인 경우로, 플레이어가 첫 턴에 딜러에게서 더미 카드를 받고 그 더미 카드를 다시 딜러에게 돌려준다.