메모리: 114328 KB, 시간: 112 ms
구현
승현이는 앞면과 뒷면이 있는 카드 n장을 가지고 있습니다. 각 카드의 앞면에는 1 이상 2222 이하의 정수가 적혀 있으며, 이 수는 카드마다 서로 다릅니다. 각 카드의 뒷면에는 동물 그림이 그려져 있으며, 이 그림 역시 카드마다 서로 다릅니다.
가능한 카드의 예시입니다. 왼쪽 그림은 앞면, 오른쪽 그림은 뒷면입니다.
승현이는 카드들을 바닥에 뒷면이 보이도록 일렬로 늘어 놓고, 차례대로 1 이상 n 이하의 자연수 번호를 붙였습니다. 이 중 i번 카드의 앞면에 적혀 있는 수를 ci로 둡시다. 승현이는 바닥에 카드가 정확히 한 장 남을 때까지 아래와 같은 행동을 반복합니다.
- 승현이는 마음에 드는 서로 다른 카드 두 장을 앞면이 보이도록 뒤집어 봅니다.
- 승현이는 앞면에 더 작은 수가 적혀 있는 카드를 주머니 속에 넣고, 더 큰 수가 적혀 있는 카드는 다시 바닥에 뒷면이 보이도록 내려놓습니다.
- 카드가 두 장 이상 남았다면 1번으로 돌아갑니다. 카드가 정확히 한 장 남았다면, 승현이는 주머니 속에 있는 카드들을 꺼내 앞면에 적혀 있는 수들의 합을 구합니다.
승현이는 큰 수가 좋아서, 마지막에 주머니 속에 들어있는 카드들에 적혀 있는 수들의 합을 가능한 한 크게 하고자 합니다. (뒷면에 그려진 동물 그림이 서로 다르므로 방법만 알고 있다면 충분히 가능합니다!) 승현이를 도와주세요.
첫 번째 줄에 카드의 수를 나타내는 자연수 n이 주어집니다. (1 ≤ n ≤ 2222)
두 번째 줄에 c1,c2,⋯,cn이 공백을 사이에 두고 차례대로 주어집니다.
첫 번째 줄에 가능한 최대 합을 출력합니다.