package main import ( "fmt" ) func scan() (N int, V []int) { fmt.Scan(&N) for i := 0; i < N; i++ { var v int fmt.Scan(&v) V = append(V, v) } return } func max(a, b int) int { if a > b { return a } return b } func main() { N, V := scan() // N := 3 // V := []int{1, 2, 3} // N := 4 // V := []int{1, 2, 3, 4} // N := 4 // V := []int{5, 4, 4, 9} // N := 7 // V := []int{1, 2, 9, 10, 1, 1, 4} // N := 1 // V := []int{100} // 皿Nが与えられた場合のおいしさの最大値のマッピングリスト // NはN-1の結果から得られるので、全探索は必要ない var dp [1000][1000 * 100]bool for i := 0; i < N; i++ { dp[i][V[i]] = true if i-2 >= 0 { for j := 0; j < len(dp[i-2]); j++ { if dp[i-2][j] { dp[i][V[i]+j] = true } } } if i-3 >= 0 { for j := 0; j < len(dp[i-3]); j++ { if dp[i-3][j] { dp[i][V[i]+j] = true } } } } for i := len(dp[N-1]) - 1; i >= 0; i-- { if dp[N-1][i] { fmt.Print(i) break } } }