같이 던전 도실래요?

마비노기 모바일에 새 던전이 추가되었다. $2N$명의 플레이어가 $2$인용 파티 던전에 도전하려고 한다. 각 플레이어마다 플레이 가능 시간이 분 단위로 주어지며, $2$인 파티의 플레이 가능 시간은 두 플레이어의 플레이 가능 시간 중 작은 값이다.

각 플레이어는 정확히 하나의 파티에 참여해야 한다. 따라서, 총 $N$개의 $2$인 파티가 만들어져야 한다.

두 명의 플레이어가 한 파티를 만들 때, 파티 시너지는 다음과 같이 정의된다.

던전은 무한한 개수의 방으로 이루어져 있고, 항상 첫 번째 방부터 시작하여 차례대로 방을 방문한다. 방 하나를 클리어하는 데에는 모두 동일하게 $M$분이 걸린다. 방 사이를 이동하는 데에는 시간이 걸리지 않는다.

각 파티는 파티의 플레이 가능 시간 동안만 던전 공략이 가능하며, 플레이 종료 시점까지 공략이 끝나지 못한 방은 클리어하지 못한 것으로 간주된다. 플레이 종료 시점과 클리어 시점이 동일하다면, 그 방은 클리어한 것임에 유의하라.

파티의 최종 스코어는 다음과 같이 계산된다.

파티를 적절히 구성하여 모든 파티의 최종 스코어의 총합을 최대화하는 프로그램을 작성하라.

입력 형식

첫 줄에 파티 던전의 수를 나타내는 정수 $N$과 던전의 각 방을 클리어하는 데 필요한 시간을 나타내는 정수 $M$이 주어진다. ($1 \le N \le 100\,000;$ $1 \le M \le 200\,000$)

그다음 줄에 각 플레이어가 플레이할 수 있는 시간을 나타내는 $2N$개의 정수 $A_1, A_2, \cdots, A_{2N}$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 200\,000$)

출력 형식

첫 줄에 모든 파티의 최종 스코어의 총합의 최댓값을 출력한다.

예제 1

2 2
3 3 5 5

26

예제 2

1 1
1000 1000

2000000

예제 3

5 1
1 2 1 2 1 2 1 2 1 2

22

예제 설명

• 예제 1에서는 플레이 가능 시간이 같은 플레이어끼리 파티를 만들면, 파티 시너지는 각각 $(3 + 3) - |3 - 3| = 6$, $(5 + 5) - |5 - 5| = 10$이 된다.

  플레이 가능 시간이 $3$인 파티는 $1$개의 방을 클리어하고, 플레이 가능 시간이 $5$인 파티는 $2$개의 방을 클리어하므로 최종 스코어 총합은 $6 \times 1 + 10 \times 2 = 26$이다.

• 예제 2에서는 파티를 만들 수 있는 방법이 하나뿐이므로, 파티 시너지는 $(1\,000 + 1\,000) - |1\,000 - 1\,000| = 2\,000$이고, 이렇게 구성한 파티는 $1\,000$개의 방을 클리어할 수 있다. 따라서, 최종 스코어는 $2\,000 \times 1\,000 = 2\,000\,000$이다.

• 예제 3에서도 플레이 가능 시간이 같은 플레이어끼리 파티를 만들면, 파티 시너지가 $(2 + 2) - |2 - 2| = 4$인 파티가 $2$개, $(1 + 1) - |1 - 1| = 2$인 파티가 $2$개가 된다.

  나머지 $1$개의 파티는 플레이 가능 시간이 $1$인 플레이어와 $2$인 플레이어로 이루어지며, 이 파티의 파티 시너지는 $(1 + 2) - |1 - 2| = 2$이고 파티의 플레이 가능 시간은 $1$이다.

  플레이 가능 시간이 $2$인 파티는 $2$개의 방을 클리어할 수 있고, 플레이 시간이 $1$인 파티는 $1$개의 방을 클리어할 수 있으므로, 최종 스코어 총합은 $2 \times (4 \times 2) + 2 \times (2 \times 1) + (2 \times 1) = 22$이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설