20162번 - 간식 파티

서울이는 입맛이 까다로운 고양이다. 입맛이 까다로운 서울이는 전에 먹었던 간식보다 더 맛있는 간식만 먹는다. 서울이는 간식의 평점이 높을수록 맛있다고 느낀다.

집사는 서울이에게 N 일 동안 간식 파티를 열어주려고 한다. 간식 파티가 열리는 날에 서울이는 간식을 먹을 수도 있고, 먹지 않을 수도 있지만, 간식은 하루에 하나만 지급된다. 집사는 이왕이면 서울이에게 최대한 만족스러운 간식 파티를 열어주기를 원한다. 최대한 만족스러운 간식 파티는 만족도가 최대인 간식 파티를 말하는데, 파티의 만족도는 다음과 같이 계산한다.

(파티의 만족도) = (파티가 열리는 동안 서울이가 먹은 모든 간식의 평점의 합)

집사는 INFJ라 계획 세우는 것을 좋아하기 때문에, 파티 일수와 각 날짜에 줄 수 있는 간식의 평점을 기록한 계획표를 만들려고 한다.

파티 일정을 짜는 것은 집사가 좋아하는 일이라 바쁜 와중에도 기꺼이 할 수 있지만, 짜여진 계획을 보고 간식 파티의 최대 만족도를 미리 계산하는 것은 도저히 할 시간이 없다. 집사는 서울이 밥 주기, 서울이 놀아주기, 서울이 화장실 치워주기 등 해야 할 일이 너무 많기 때문이다.

바쁜 집사를 위해 계획표를 보고 간식 파티의 최대 만족도를 미리 계산하는 프로그램을 만들어주자. 단, 간식 파티가 열리기 전 서울이가 먹은 마지막 간식의 평점은 0점이다.

첫째 줄에 정수 N (1 ≤ N ≤ 1,000) 이 주어진다.

둘째 줄부터 N + 1번째 줄까지 간식의 평점이 주어진다. i + 1 (1 ≤ i ≤ N) 번째 줄은 파티 i 번째 날에 줄 수 있는 간식의 평점을 의미하며, 주어지는 평점은 모두 100,000을 넘지 않는 양의 정수이다.

첫째 줄에 입력으로 주어진 간식 파티 계획표의 최대 만족도를 출력한다.