꽃가게의 쇼 윈도우를 꾸미려고 한다. 우리는 여러개의 꽃과 꽃병을 가지고 있다. 꽃 들은 서로 다른 꽃이고 꽃병들은 선반 위에 고정되어 있다. 제일 왼쪽에 있는 꽃병이 1 번 꽃병이고, 다음이 2 번 순으로 번호가 부여되어 있다. 꽃들도 1 번 부터 번호가 부여 되어 있다.
꽃에 부여된 번호는 중요한 의미를 가진다. 1 번 꽃은 2 번 꽃의 왼쪽에 위치해야 하고, 마찬가지로 3 번 꽃 다음에 4 번 꽃이 위치해야 한다. 번호가 큰 꽃이 번호가 작은 꽃의 왼 쪽에 위치할 수는 없다.
예를들어, 1 번 꽃을 장미라 하고 2 번 베고니아, 3 번 꽃을 카네이션이라 하면 장미는 카네이션 왼쪽 꽃병에 위치해야 하며 베고니아는 카네이션의 왼쪽 꽃병에 위치해야 한다.
만약 꽃병이 꽃보다 많으면 채워지지 않는 꽃병이 존재할 수 있다.
꽃병에 있는 꽃다발들은 다음과 같은 미적 점수표를 가지고 있다.(정수)
| 꽃 병 | ||||||
| 1 | 2 | 3 | 4 | 5 | ||
| 꽃 | 1 (장미) | 7 | 23 | -5 | -24 | 16 |
| 2 (베고니아) | 5 | 21 | -4 | 10 | 23 | |
| 3(카네이션) | -21 | 5 | -4 | -20 | 20 | |
위의 테이블에서 장미는 2 번 꽃병에 위치하면 가장 좋고, 4 번 꽃병에 위치하면 가장 최악이다. 가장 바람직한 결과를 얻기 위해서는 꽃들의 순서를 유지하면서 미적 점수의 합이 최대가 되어야 한다. 최대치가 여러 개 나온다면 하나만을 출력한다.
단, 꽃은 100 개를 넘지 않고, 꽃병의 수는 꽃다발의 수보다 최소 크거나 같고 100 개를 넘지 않는다.
입력 3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20 출력 53
출처: ioi 기출