33960번 - 사과 게임

문제

사과 게임은 직사각형 격자 형태의 게임판에 배치된 사과를 많이 제거해 최대한 높은 점수를 얻는 것이 목표인 게임이다. 눈이 아프다는 단점이 있지만 간단한 규칙과 생각보다 높은 난이도로 많은 인기를 끌었다.

사과 게임이 SNS와 인터넷 커뮤니티 등을 중심으로 전국적으로 유행하게 되자 포닉스는 주어진 게임판에서 얻을 수 있는 최대 점수를 계산하는 프로그램을 만들어 SNS에 점수를 자랑하고 싶어졌다. 하지만 아무리 생각해도 방법이 떠오르지 않아 화가 난 포닉스는 사과가 들어있는 게임판을 발로 걷어차버렸다! 그러자 사과들이 전부 바닥으로 굴러떨어져 일직선으로 배치되었다.

이를 본 포닉스는 문득 2차원의 직사각형 게임판이 아닌 1차원의 일직선 게임판에서는 최대 점수를 구할 수 있을지 궁금해졌다. 바뀐 게임판에서의 게임 규칙은 다음과 같이 정리할 수 있다.

• $N$개의 사과가 게임판에 일직선으로 배치되어 있고, 각 사과에는 1ドル$부터 9ドル$까지의 수 중 하나가 적혀있다.
• 연속한 사과를 하나 이상 선택한다. 두 사과 사이에 다른 사과가 없을 경우 두 사과는 연속한다.
• 선택한 사과에 적힌 수의 합이 정확히 10ドル$일 경우 선택한 사과를 모두 없앤 뒤 1점을 획득한다.
• 더이상 사과를 없앨 수 없을 때까지 시행을 반복한다.

게임의 예시

고민하느라 지쳐버린 포닉스를 도와 답을 찾아보자!

입력

첫 번째 줄에 사과의 개수 $N$이 주어진다. $(1\le N\le 500)$

두 번째 줄에 각 사과에 적힌 정수 $A_1,\cdots ,A_N$이 공백으로 구분되어 주어진다. $(1\le A_i\le 9)$

출력

주어진 배치의 게임판에서 얻을 수 있는 점수의 최댓값을 출력한다.

제한

노트

실제로 플레이 가능한 원본 사과 게임과는 점수 계산 방식이 다름을 유의하라.