음료수 |
---|
한 음료수 회사에서 시식회를 열었다. 그 곳에 갔더니, 테이블 위에 음료수가 일렬로 놓여 있었다. 여기에는 다음과 같은 두 가지 규칙이 있다.
1부터 n까지의 번호가 붙어 있는 n개의 음료수가 순서대로 테이블 위에 놓여 있고, 각 음료수의 양이 주어졌을 때, 가장 많은 양의 음료수를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 6개의 음료수 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 음료수가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 음료수 잔을 선택하면 총 음료수 양이 33으로 최대로 마실 수 있다. |
입력 | |
---|---|
첫째 줄에 음료수의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 음료수 잔에 들어있는 음료수의 양이 순서대로 주어진다. 음료수의 양은 1,000 이하의 정수이다. |
출력 | |
---|---|
첫째 줄에 최대로 마실 수 있는 음료수의 양을 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 6 6 10 13 9 8 1 | |
출력 | 33 |