시상품

미샤는 지능 쇼의 시상식에 참가한다. 시상 과정에서 상품이 하나씩 차례로 제안된다. 각 상품에는 가격이 있다. 미샤는 제안받은 상품마다 받을지 말지를 밝혀야 한다. 받거나 넘긴 뒤에는 다음 상품이 제시되며, 이전 상품으로 돌아가 결정을 바꿀 수 없다.

미샤는 첫 번째로 받는 상품으로 아무 상품이나 고를 수 있다. 그 뒤로는 직전에 받은 상품보다 가격이 엄격히 큰 상품만 받을 수 있다.

미샤는 쇼의 대본을 미리 보아서 상품 가격과 제안되는 순서를 알고 있다. 받는 상품 가격의 합이 최대가 되도록 상품을 고르는 것을 도와달라.

첫 줄에 상품의 개수 $n$이 주어진다 ($1 \le n \le 1000$). 둘째 줄에는 상품의 가격 $a_1, a_2, \ldots, a_n$이 미샤에게 제시되는 순서대로 주어진다 ($1 \le a_i \le 10^9$).

미샤가 받을 수 있는 상품 가격 합의 최댓값을 한 줄에 출력한다.